DFS+BFS-判断矩阵中块的个数

题目大意：求矩阵中块的个数

　　如6*7矩阵：

　　0 1 1 1 0 0 1

　　0 0 1 0 0 0 0

　　0 0 0 0 1 0 0

　　0 0 0 1 1 1 0

　　1 1 1 0 1 0 0

　　1 1 1 1 0 0 0

　　此矩阵中 块“1”的个数为4。

• 给出DFS做法

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int m,n;//m行n列
 4 bool visit[20][20]=false;
 5 int map_[20][20]={0};
 6 void DFS(int x,int y){
 7     int next[4][2]={0,1,0,-1,1,0,-1,0};//四个方向
 8     for(int i=0;i<4;i++){
 9         int tx=x+next[i][0];
10         int ty=y+next[i][1];
11         if(visit[tx][ty]==true||tx<1||ty<1||tx>m||ty>n) continue;//剪枝
12         if(visit[tx][ty]==false&&map_[tx][ty]==1){
13             visit[tx][ty]=true;
14             DFS(tx,ty);
15         }
16     }
17 }
18 int main(){
19     while(cin>>m>>n){
20         memset(visit,false,sizeof(visit));
21         memset(map_,0,sizeof(map_));
22         for(int i=1;i<=m;i++){
23             for(int j=1;j<=n;j++){
24                 cin>>map_[i][j];//初始化地图
25             }
26         }
27         int cnt=0;
28         for(int i=1;i<=m;i++){
29             for(int j=1;j<=n;j++){
30                 if(visit[i][j]==false&&map_[i][j]==1){
31                     //如果未被访问到 并且是能访问到的地方
32                     cnt++;
33                     DFS(i,j);
34                 }
35             }
36         }
37         cout<<cnt<<endl;
38     }
39     return 0;
40 }

•  BFS-宽度优先搜索做法：值得注意的是 BFS中设置inqueue数组是判断节点是否已入过队，而不是节点 是否已被访问（visit）。因为如果设置成是否被访问，那么可能存在某个结点已在队列中 缺未被访问 则其他节点就可访问到此节点，就会导致很多节点反复入队，这样的效率显然不如设置成是否入过队高。

   1 #include<bits/stdc++.h>
   2 using namespace std;
   3 
   4 const int maxn=20;
   5 bool inqueue[maxn][maxn]={false};
   6 int m,n;
   7 int map_[maxn][maxn]={0};
   8 int next[4][2]={0,1,1,0,0,-1,-1,0};//4个方向
   9 struct Point{
  10   int x;
  11   int y;
  12   Point(int c,int d):x(c),y(d){}
  13 };
  14 
  15 void BFS(int x,int y){
  16     queue<Point>q ;
  17     q.push(Point(x,y));//将节点入队
  18     inqueue[x][y]=true;//标记已经入过队
  19     while(!q.empty()){
  20         Point top=q.front();
  21         q.pop();
  22         for(int i=0;i<4;i++){
  23             int tx=top.x+next[i][0];
  24             int ty=top.y+next[i][1];
  25             //如果超过边界；不能访问到；已经入队过 ---那么就跳过。
  26             if(tx<1||ty<1||tx>m||ty>n||map_[tx][ty]==0||inqueue[tx][ty]==true) continue;
  27             //否则---剩下的是合法的能访问到的
  28             inqueue[tx][ty]=true;//标记入队
  29             q.push(Point(tx,ty));
  30         }
  31     }
  32 }
  33 
  34 int main(){
  35     while(cin>>m>>n){
  
          memset(map_,0,sizeof(map_));
  38         memset(inqueue,false,sizeof(inqueue));
  39         for(int i=1;i<=m;i++){
  40             for(int j=1;j<=n;j++){
  41                 cin>>map_[i][j];//初始化地图
  42             }
  43         }
  44         int cnt=0;
  45         for(int i=1;i<=m;i++){
  46             for(int j=1;j<=n;j++){
  47                 if(inqueue[i][j]==false&&map_[i][j]==1){
  48                     //如果未被访问到 并且是能访问到的地方
  49                     cnt++;
  50                     BFS(i,j);
  51                 }
  52             }
  53         }
  54         cout<<cnt<<endl;
  55     }
  56     return 0;
  57 }

   

DFS+BFS-判断矩阵中块的个数

原文：https://www.cnblogs.com/YanShaoDian/p/12686135.html