代码随想录|图论|10水流问题

leetcode:103. 水流问题

题目

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。

矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

输入描述：

第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。

后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。

输出描述：

输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。

思路

暴力解法

就是遍历图中的每一个节点，用dfs或者bfs判断，从这个点扩散，是否可以到达第一组边界和第二组边界。

#include <bits/stdc++.h>
using namespace std;int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{// 终止条件if (visited[x][y])return;visited[x][y] = true;for (int i = 0; i < 4; i++){int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())continue;if (grid[x][y] < grid[nextx][nexty])continue; // 高度不合适dfs(grid, visited, nextx, nexty);}
}bool isResult(vector<vector<int>> &grid, int x, int y)
{vector<vector<bool>> visited(n, vector<bool>(m, false));// 将从x y出发可以到达的所有节点标记上dfs(grid, visited, x, y);bool isFirst = false;bool isSecond = false;// 判断从x，y出发，是否可以到达第一组边界和第二组边界for (int j = 0; j < m; j++){if (visited[0][j]){isFirst = true;break;}}for (int i = 0; i < n; i++){if (visited[i][0]){isFirst = true;break;}}for (int j = 0; j < m; j++){if (visited[n - 1][j]){isSecond = true;break;}}for (int i = 0; i < n; i++){if (visited[i][m - 1]){isSecond = true;break;}}if (isFirst && isSecond)return true;return false;
}int main()
{cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> grid[i][j];}}// 遍历每一个点，是否可以同时到达第一组边界和第二组边界for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (isResult(grid, i, j))cout << i << " " << j << endl;}}return 0;
}

dfs里面需要注意的是

if (grid[x][y] < grid[nextx][nexty])continue; // 高度不合适

因为水流只能往高度低的地方流动。

暴力解法用了n*m次dfs，复杂度是非常高的O(m^2 * n^2)。

逆向解法

一个点出发，要能到达两个地方，反过来想就是，两个地方出发，如果都经过这个点，那么这个点就是我们需要的。

所以dfs只要从第一组边界来一趟，再从第二组边界来一趟，他们的交集，就是最终答案，如图：

代码：

// ====================================== 逆向======================================
#include <bits/stdc++.h>
using namespace std;int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};// dfs逆向流水，将可以逆向流到的节点进行标记
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{// 终止条件if (visited[x][y])return;// 处理当前节点visited[x][y] = true;// 处理相邻节点for (int i = 0; i < 4; i++){int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())continue;// 逆流向上的条件是下一个点要 >= 当前点，所以先把不满足的情况排除掉，再进行dfsif (grid[x][y] > grid[nextx][nexty])continue;dfs(grid, visited, nextx, nexty);}
}int main()
{cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> grid[i][j];}}// 标记从第一组边界开始出发，可以到达的节点。vector<vector<bool>> first_vis(n, vector<bool>(m, false));// 标记从第二组边界开始出发，可以到达的节点。vector<vector<bool>> second_vis(n, vector<bool>(m, false));// 最左列（第一组边界）、最右列（第二组边界）for (int i = 0; i < n; i++){dfs(grid, first_vis, i, 0);dfs(grid, second_vis, i, m - 1);}// 最上行（第一组边界）、最下行（第二组边界）for (int j = 0; j < m; j++){dfs(grid, first_vis, 0, j);dfs(grid, second_vis, n - 1, j);}// 如果某个节点是第一组边界出发和第二组边界出发都可以到达的点for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (first_vis[i][j] == true && second_vis[i][j] == true){cout << i << " " << j << endl;}}}return 0;
}

 逆向求解跟暴力求解的区别：

1. dfs里面的水流流向判断条件反过来。
2. 暴力求解是对每一个点都使用dfs，逆向求解只对第一组边、第二组边使用dfs。

总结

谁能想到？

参考资料

103. 水流问题