太平洋大西洋水流问题

时间:2025-04-07 21:45:34
  • #include<iostream>
  • using namespace std;
  • int height[201][201], book[201][201];
  • int m, n,num=1;
  • //当前点坐标
  • void dfs(int x, int y) {
  • int i, j, k, tx, ty;
  • //定义四个方向
  • int next[4][2] = {
  • {0,1},{1,0},{0,-1},{-1,0}
  • };//右下左上
  • //尝试四个方向是否能走
  • for (k = 0;k < 4;k++) {
  • tx = x + next[k][0];
  • ty = y + next[k][1];
  • //如果右边点大于当前点则可以流经然后再判断下一个点是否满足条件,找到满足条件的book都置
  • if (tx>=0 && ty>=0 && tx<n && ty<m &&height[tx][ty] >= height[x][y]&&book[tx][ty]==0) {
  • book[tx][ty] =1;
  • dfs(tx, ty);
  • }
  • }
  • return;
  • }
  • int main() {
  • int i, j, a[201][201] = { 0 }, b[201][201];
  • //输入行列
  • cin >> n >> m;
  • //输入数据
  • for (i = 0;i < n;i++)
  • for (j = 0;j < m;j++)
  • cin >> height[i][j];
  • //满足条件的点进入搜索(四周的点分为四个部分)
  • //
  • for (i = 0;i < n;i++) {
  • book[0][i] = 1;
  • dfs(0, i);
  • }
  • //
  • for (i = 1;i < n;i++){
  • book[i][0] = 1;
  • dfs(i, 0);}
  • for (i = 0;i < n;i++)
  • for (j = 0;j < m;j++)
  • a[i][j] = book[i][j];//将book中走过的全部赋值给a数组,暂存
  • //清空book标记数组
  • for (i = 0;i < n;i++) {
  • for (j = 0;j < m;j++)
  • book[i][j] = { 0 };
  • }
  • cout << endl;
  • //
  • for (i = 1;i < n;i++) {
  • book[4][i] = 1;
  • dfs(n-1, i);
  • }
  • //
  • for (i = 1;i < n - 1;i++) {
  • book[i][4] = 1;
  • dfs(i, n-1);
  • }
  • //找a和book数组重合的部分进行输出
  • for (i = 0;i < n;i++)
  • for (j = 0;j < m;j++)
  • {
  • if (a[i][j] == book[i][j])
  • cout << i << " " << j << endl;
  • }
  • return 0;
  • }
  • 5 5
  • 1 2 2 3 5
  • 3 2 3 4 4
  • 2 4 5 3 1
  • 6 7 1 4 5
  • 5 1 1 2 4