BFS识别矩阵中的块数

- 日理万妓 2022-04-25 01:00 163阅读 0赞

题目描述：  
给出一个m\*n的矩阵，矩阵中的元素为0或1.称位置（x,y）与其上下左右四个位置是相邻的。如果矩阵中有若干个1相邻，则称这些1构成了一个块。求给定矩阵中的块数。  
输入：  
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

输出：4

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]

> 【思路】用队列进行存储，当矩阵中的值为1并且矩阵中的值没有访问过，块就加1。然后使用BFS访问和他相邻的元素，如果发现值为1并且没有被访问过，就可以入队，指导将相邻的所有1访问完，此时BFS结束，但是相邻的1都算在一个块中.然后再重新开始访问。  
>

#include<cstdio>
    #include<iostream>
    #include<queue>
    #define MAXN 100
    using namespace std;
    struct node{
    	int x,y;//位置x,y 
    }Node; 
    
    int matrix[MAXN][MAXN];
    bool book[MAXN][MAXN]={false};//没有访问过
    int X[4]={0,0,1,1};//增量数组 
    int Y[4]={1,-1,0,0};
    
    int m,n;//m行，n列的矩阵 
    bool judge(int x, int y)//判断坐标(x,y)是否需要被访问 
    {
    	if(x>m || x<0 || y>n || y<0) return false;
    	if(book[x][y]==true || matrix[x][y]==0) return false;
    	return true; 
    } 
    
    void BFS(int x, int y)
    {
    	queue<node> Q;//定义队列
    	Node.x = x;//当前节点的坐标为(x,y) 
    	Node.y = y;
    	Q.push(Node);
    	book[x][y] = true;
    	while(!Q.empty())
    	{
    		node top = Q.front();//取出队首元素
    		Q.pop();//将队首元素出队
    		for(int i = 0; i < 4; ++i)
    		{
    			int newX = top.x + X[i];//遍历队首元素相邻的元素 
    			int newY = top.y + Y[i];
    			if(judge(newX,newY)) //如果需要被访问
    			{
    				Node.x = newX;
    				Node.y = newY;
    				Q.push(Node);//将和队首元素相邻的元素入队 
    				book[newX][newY] = true; //已被访问 
    			}
    		} 
    	}
    }
    
    int main()
    {
    	scanf("%d%d",&m,&n);
    	for(int i = 1; i <= m; ++i)
    	{
    		for(int j = 1; j <= m; ++j)
    		{
    			scanf("%d",&matrix[i][j]);
    		}
    	}
    	int sum = 0;
    	for(int x = 1; x <= m; ++x)
    	{
    		for(int y = 1; y <= n; ++y)
    		{
    			if(matrix[x][y] == 1 && book[x][y] == false)
    			{
    				sum++;//块数加1 
    				BFS(x,y);//访问整个块，将该块所有"1"的book都标记为true 
    			}
    			
    		}
    	}
    	printf("%d\n",sum);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20220210/dbfda81c352041f5a2c868349f52a493.png