Informatics Orsay all in one 1335: [example 2-4] connected block

【 Topic link 】

ybt 1335：【 example 2-4】 Connected block

【 Topic test site 】

1. Search for ： Connected block problem

【 Their thinking 】

Set array vis,vis[i][j] Express (i,j) The location has been visited .
Traverse every location in the map , Try searching from every location .
If the location is not 0 And I haven't visited , Then access the location , And try to search from its top, bottom, left and right .
When looking at a new location , If the location is within the map , Not visited and not 0, Then continue to search from this location .
In the process of traversing the grid , A successful search can determine a connected block , Count the number of connected blocks , Is the result .
The search method can be deep search or wide search .

【 Solution code 】

solution 1： Deep search

#include<bits/stdc++.h>
using namespace std;
#define N 105
int n, m, a[N][N], ans;//ans: Number of connected blocks 
bool vis[N][N];//vis[i][j]:(i,j) Have you ever visited  
int dir[4][2] = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};
void dfs(int sx, int sy)
{
    
	for(int i = 0; i < 4; ++i)
	{
    
		int x = sx + dir[i][0], y = sy + dir[i][1];
		if(x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == false && a[x][y] == 1)
		{
    // If in the map 、 Never visited 、 It's black  
			vis[x][y] = true;
			dfs(x, y);
		}
	}
}
int main()
{
    
	cin >> n >> m;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			cin >> a[i][j];
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		{
    
			if(a[i][j] == 1 && vis[i][j] == false)// If this is black and you haven't visited  
			{
    
			    vis[i][j] = true;
				dfs(i, j);
				ans++;// Each successful deep search can determine a connected block  
			}
		}
	cout << ans;
	return 0;
}

solution 2： Guang Shu

#include<bits/stdc++.h>
using namespace std;
#define N 105
struct Node
{
    
	int x, y;
	Node(){
    }
	Node(int a, int b):x(a),y(b){
    }
};
int n, m, a[N][N], ans;//ans: Number of connected blocks 
bool vis[N][N];//vis[i][j]:(i,j) Have you ever visited  
int dir[4][2] = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};
void bfs(int sx, int sy)
{
    
	queue<Node> que;
	vis[sx][sy] = true;
	que.push(Node(sx,sy));
	while(que.empty() == false)
	{
    
		Node u = que.front();
		que.pop();
		for(int i = 0; i < 4; ++i)
		{
    
			int x = u.x + dir[i][0], y = u.y + dir[i][1];
			if(x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == false && a[x][y] == 1)
			{
    
				vis[x][y] = true;
				que.push(Node(x,y));
			}
		}
	}
}
int main()
{
    
	cin >> n >> m;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			cin >> a[i][j];
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		{
    
			if(a[i][j] == 1 && vis[i][j] == false)// If this is black and you haven't visited  
			{
    
				bfs(i, j);
				ans++;// Each successful search can determine a connected block  
			}
		}
	cout << ans;
	return 0;
}