逆向思维_c++ 逆向思维

水流问题
在"我的世界"游戏中，一桶水就可以汇聚成一片湖。现在有一个 n x m 的大陆，大陆上各个单元格的高度是不一致的。大陆同时和“太平洋”与“大西洋”接壤。
（1）“太平洋”处于大陆的左边界和上边界
（2）“大西洋”处于大陆的右边界和下边界。

现在在大陆上某个坐标倒下一桶水，规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标数量。
输入

测试样例由多组测试数据组成。每组测试数据第一行输入两个正整数n（1 <= n <= 150 ） 和 m （ 1 <= m < = 150 ），代表大陆的长和宽。接下来n行，每行输入m个非负整数，代表大陆上每个单元格的高度。
输出

输出既可以流动到太平洋又可以流动到大西洋的单元格数量
样例输入 Copy

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
样例输出 Copy

7
*刚看这个题目题目是我打算从最高的去搜索，后来看了题解后发现原来是从最低的去搜；然后通过标计走过的地方来输出

#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[1000][1000];
int dir[4][2]={1,0,0,1,0,-1,-1,0};
void dfs(int x,int y){
    if(s[x][y]!='O'){
        return;
    }
    s[x][y]='p';
    for(int i=0;i<4;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(tx>=0&&ty>=0&&tx<n&&ty<m){
            dfs(tx,ty);
        }
    }
     
}
int main(){
    while(cin>>n>>m){   
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>s[i][j];
            }
        }
        for(int i=0;i<m;i++){
            dfs(0,i);
            dfs(n-1,i);
        } //标记可以到太平洋的点；
        for(int i=0;i<n;i++){
            dfs(i,0);
            dfs(i,m-1);
        }//标记可以到大西洋的点；
         
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(j!=0){
                    cout<<" ";
                }
                if(s[i][j]=='X'||s[i][j]=='O'){
                    cout<<"X";
                }
                else{
                    cout<<"O";
                }
            }
            cout<<endl;
        }
    }
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

问题 F: 被X包围的区域

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
输入

输入样例由多组数据组成。第一行输入两个正整数n，m表示边界。（1<=n,m<=100）
接下来输入n*m个’X’和’O’表示矩阵。
输出

输出一个n*m的矩阵表示填充后的矩阵。
样例输入 Copy

4 4
X X X X
X O O X
X X O X
X O X X
样例输出 Copy

X X X X
X X X X
X X X X
X O X X
这一题和上题非常相似，通过对在边缘的点向里搜进行标记最后在通过标计进行输出

#include<bits/stdc++.h>
using namespace std;
int n,m,s[160][160];
int vis[160][160];
int vis1[160][160];
int tai,xi;
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
 
int dfs(int x,int y){
    for(int q=0;q<4;q++){
        int tx=x+dir[q][0];
        int ty=y+dir[q][1];
        if(x>=0&&tx<n&&ty>=0&&ty<m&&s[x][y]<=s[tx][ty]&&vis[tx][ty]==0){
            vis[tx][ty]=1;
            dfs(tx,ty);
        } 
    }
}
int dfs1(int x,int y){
    for(int q=0;q<4;q++){
        int tx=x+dir[q][0];
        int ty=y+dir[q][1];
        if(x>=0&&tx<n&&ty>=0&&ty<m&&s[x][y]<=s[tx][ty]&&vis1[tx][ty]==0){
            vis1[tx][ty]=1;
            dfs1(tx,ty);
        } 
    }
}
int main(){
    while(cin>>n>>m){
        memset(vis,0,sizeof(vis));
        memset(vis1,0,sizeof(vis1));
        for(int q=0;q<n;q++){
            for(int w=0;w<m;w++){
                cin>>s[q][w];
            }
        }
        for(int q=0;q<n;q++){
            for(int w=0;w<m;w++){
                if(q==0||w==0){
                    vis[q][w]=1;
                    dfs(q,w);
                }
                if(q==n-1||w==m-1){
                    vis1[q][w]=1;
                    dfs1(q,w);
                }
            }
        }
        int sum=0;
        for(int q=0;q<n;q++){
            for(int w=0;w<m;w++){
                if(vis[q][w]==1&&vis1[q][w]==1){
                    sum++;
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61