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;
// 逆流向上的条件是下一个点要 >= 当前点，所以先把不满足的情况排除掉，再进行dfs
if (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;
}逆向求解跟暴力求解的区别：
- dfs里面的水流流向判断条件反过来。
- 暴力求解是对每一个点都使用dfs，逆向求解只对第一组边、第二组边使用dfs。
总结
谁能想到？