深搜和宽搜-蓝桥杯例题的应用

题目

dfs做法 一定记得return回溯和恢复现场！！！

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
#include<bits/stdc++.h>
using namespace std;

int n;
char a[1010][1010]; //地图
int vis[1010][1010]={0};  //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag;  //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
    vis[x][y] = 1;      //标记这个'#'被搜过。注意为什么可以放在这里
    cout<<x<<y<<endl;;
    if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')
        flag = 1;       //上下左右都是陆地，不会淹没
    for(int i = 0; i < 4; i++){ //继续DFS周围的陆地
        int nx = x + d[i][0], ny = y + d[i][1];
       cout<<"text:=="<<nx<<" "<<ny<<endl;
        if(vis[nx][ny]==0 && a[nx][ny]=='#') //继续DFS未搜过的陆地，目的是标记它们
            dfs(nx,ny);
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> a[i][j];
    int ans = 0 ;
    for(int i = 0; i < n; i++)  //DFS所有像素点
        for(int j = 0; j < n; j++)
            if(a[i][j]=='#' && vis[i][j]==0){
                flag = 0;
                dfs(i,j);
                if(flag == 0)  //这个岛全部被淹
                    ans++;     //统计岛的数量
            }
    cout<<ans<<endl;
     for(int i = 0; i <n; i++)
        for(int j = 0; j <n; j++)
           {cout<<vis[i][j]<<" ";if(j==n-1) cout<<endl;}
    return 0;
}

bfs做法

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;
typedef pair<int,int> PII;
int n;
char g[N][N];
bool st[N][N];
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};

int bfs(int x,int y,int &total,int &bound)
{   queue<PII> q;   //begin to bfs
    q.push({x,y});
   
    st[x][y]=true;  //  had use
    while(q.size())
      {   PII t=q.front();
          q.pop();
           bool is_water=false;
           total++;
           for(int i=0;i<4;i++)
              {    int nx=t.first+dx[i];
                   int ny=t.second+dy[i];

                   if(st[nx][ny]){  //访问过就跳过循环
                       continue;
                   }

                   if(g[nx][ny]=='.')
                       {
                           is_water=true;  //这个区域的周围是有水的
                           continue;  //是水的话就不进行入队的操作
                       }                    
                  q.push({nx,ny});
                  st[nx][ny]=true;  
              }
              if(is_water)
                {

                    bound++;
                }


          

      }


}






int main()
{   cin>>n;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
           cin>>g[i][j];

     int ans=0;

     for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            {  if(!st[i][j]&&g[i][j]=='#')
                  {   int start=0; int boud=0;
                      bfs(i,j,start,boud);
                      if(start==boud)  //靠海的格子等于山的数量
                         ans++;
                     


                  }
             



            }      

cout<<ans;

    return 0;
}