【BFS】求“块”的个数

偏执的太偏执、 2023-02-13 14:53 9阅读 0赞

题目

给出一个m*n的矩阵，矩阵中元素为0或1。称位置（x，y）与其上下左右资格位置是相邻的。
    如果矩阵中有若干个1是相邻的，则称这些1构成了一个“块”，求给定矩阵中块的个数。

输入

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

输出

#include <cstdio>
    #include <queue>
    using namespace std;
    const int maxn = 100;
    
    int n,m;  //m*n矩阵 
    int matrix[maxn][maxn];  //01矩阵 
    int count = 0;  //统计“块”的数量 
    bool inqueue[maxn][maxn] = {
        false}; //记录对应位置是否入过队列 
    
    int X[4] = {
        0,0,1,-1}, //分别表示(0,1),(0,-1),(1,0),(-1,0)四个方向 			  
        Y[4] = {
        1,-1,0,0}; 
    
    struct Node{
         
     int x,y; //表示位置（x，y） 
    };
    
    //判断位置（x，y）是否需要访问 
    bool judge(int x,int y){
         
      if(x < 0 || x > m || y < 0 || y > n) //位置出界 
        return false;
      if(matrix[x][y] == 0 || inqueue[x][y] == true)  //当前位置为0，或者已入过队列 
       return false;
      return true;
    }
    
    void BFS(int x,int y){
        
      int i;
      queue<Node> Q; //定义队列Q 
      Node N;  //定义结点N 
      N.x = x;
      N.y = y; //当前结点坐标为（x，y） 
      Q.push(N); //将N入队列 
      inqueue[x][y] = true; //标记位置（x，y）已入过队列 
      while(!Q.empty()){
          
        Node top = Q.front(); //取队首元素 
        Q.pop();  //记录队首元素后出队列 
        for(i = 0; i < 4; i++){
         //分别判断当前位置的四个方向 	  
          int newX = top.x + X[i]; 
          int newY = top.y + Y[i]; //记录相邻位置 
          if(judge(newX,newY)){
          //新位置可以访问 
            N.x = newX;
            N.y = newY;
            Q.push(N);  //将新位置结点入队列 
            inqueue[newX][newY] = true; //标记已入过队列 
           }
        }
      }
    }
    
    int main(int argc, char** argv) {
        
      int i,j;
      scanf("%d%d",&m,&n); 
      for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
           scanf("%d",&matrix[i][j]); //输入m*n矩阵 
      for(i = 0; i < m; i++)
        for(j = 0; j < n; j++){
        
             if(matrix[i][j] == 1 && inqueue[i][j] == false){
        
             //元素是1且没有入过队列 
             count++; //块数加一 
             BFS(i,j); //访问整个块，将块中所有元素为1的位置标记为入过队列 
            } 
         }
      printf("%d\n",count);
      return 0;
    }