当前位置：首页 > news >正文

06高山流水图论

news 2026/5/24 20:15:10

\103. 高山流水

题目描述

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

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

输入描述

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

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

输出描述

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

输入示例

输出示例

提示信息

图中的蓝色方块上的雨水既能流向第一组边界，也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。

数据范围：

1 <= M, N <= 100。

//这个方法比较好，时间复杂度较低，且也没有增加难度
#include<iostream> 
#include<vector>
using namespace std;
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
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]){dfs(grid,visited,nextx,nexty);}}
}
int main(void)
{int n,m;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>> firstorder(n,vector<bool>(m,false));vector<vector<bool>> secondorder(n,vector<bool>(m,false));for(int i=0;i<n;i++){dfs(grid,firstorder,i,0);dfs(grid,secondorder,i,m-1);}for(int j=0;j<m;j++){dfs(grid,firstorder,0,j);dfs(grid,secondorder,n-1,j);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(firstorder[i][j]==true && secondorder[i][j]==true){cout << i << " " << j << endl;}}}return 0;
}

本方法是从边界逆向流水（从低到高），将从边界能流到的地方做一个标记（左上一个，右下一个），当一个点既能被第一组边界流到，也能被第二组边界流到，那么该点符合题意，直接输出

//直接dfs暴力法（更加耗时）
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};// 从 x，y 出发 把可以走的地方都标记上
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 >= n || nexty < 0 || nexty >= m) continue;if (grid[x][y] < grid[nextx][nexty]) continue; // 高度不合适dfs (grid, visited, nextx, nexty);}return;
}
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;}}}
}