Problem_J

究极签到题，在这里水个分享

题目集链接

:no_mouth:大致题意

模拟雨水在屋顶的流动，从高往低处流

同时，屋顶会有一些漏洞，雨水会从漏洞进入屋内

问，最后每个漏洞会漏进多少毫升的雨水？

解题思路

==DFS + 递归==

直接暴力枚举出每个点的水流路径（终点是漏水点），根据路径的数量计算每个路径需要分配的水量，并且从下面的题意中

“Furthermore, the water equally divides among all possible directions.”

我们可以知道每个路径分配的雨水量是均分的，所以我们完全可以声明一个变量ok去存储一共需要分配多少路径（ok的最大值是4）

最后为每个路径分配的水量为 $\frac{总水量} {ok}$，本道题结束

Code

• AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 505;
int a[MAXN][MAXN];  //储存屋顶矩阵
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};  //上下左右
int n;
double m;
double ans[MAXN][MAXN]; //储存每个点的雨水量

//判断水流是否能流向下一个点
bool check(int a, int b){
  if (a > b && b != -1) return true; //如果下一个点的高度小于当前点的高度，且下一个点不是边界，则返回true 
  return false;
}

void dfs(int x, int y){
  //边界条件，遇到漏水点则返回
  if (!a[x][y]) {
    return;
  }

  //储存路径数量
  int ok = 0;

  //计算当前点水流的路径数量
  for (int i = 0; i < 4; i++){
        if (check(a[x][y], a[x + dx[i]][y + dy[i]])) ok++;
    }

  //如果没有路径，则说明当前点为囤积点
  if(ok){
      //储存为每个路径分配的雨水量
      double tmp = ans[x][y] / ok;
      //为四个方向中可以流通的方向分配雨水
    for (int i = 0; i < 4; i++){        
        if (check(a[x][y], a[x + dx[i]][y + dy[i]])) {          
            ans[x + dx[i]][y + dy[i]] += tmp;
              ans[x][y] = 0;
            dfs(x + dx[i], y + dy[i]);
        }
    }
  }
}

int main(){
  cin >> n >> m;

  //初始化屋顶矩阵，将边界的值设为-1
  memset(a, -1, sizeof a);
  //初始化每个点的雨水量为 m 毫升
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++){
        ans[i][j] = m;
    }

  //输入屋顶矩阵
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        cin >> a[i][j];

  //水流开始流动
  for (int x = 1; x <= n; x++)
    for (int y = 1; y <= n; y++){
        dfs(x, y); 
    }       

  //输出结果
  for (int x = 1; x <= n; x++){
    for (int y = 1; y <= n; y++){
        if (!a[x][y])
            printf("%lf ", ans[x][y]);
        else cout << 0 << " ";
    }
    cout << endl;
  }

  return 0;
}