All in one 1329 cells (breadth first search)

Original link http://ybt.ssoier.cn:8088/problem_show.php?pid=1329

【 Title Description 】

A rectangular array consists of numbers 0 To 9 form , Numbers 1 To 9 For cells , A cell is defined as the same cell along the cell number, up and down, left and right, or cell number , Find the number of cells in a given rectangular array . Such as :

array ：

4 10
0234500067
1034560500
2045600671
0000000089

Yes 4 Cells .

【 Input 】

The first row is the row of the matrix n And column m;

Here's a n×m Matrix .

【 Output 】

Number of cells .

【 Enter a demo 】

4 10
0234500067
1034560500
2045600671
0000000089

【 Output demonstration 】

4

Examine the subject

Adjacent non-zero numbers are one cell . Count the number of cells

step

1. Defining variables

#include<iostream>
#include<queue>
using namespace std;
int a[4][2]={
   {1,0},{-1,0},{0,1},{0,-1}};
int n,m,res=0;
char s[1000][1000];
int mk[1000][1000];
struct node{   // Structure 
	int x;
	int y;
};

2. Define search function

void bfs(int x,int y)
{
	queue<node>q;
	q.push((node){x,y});
	while(q.size())
	{
		node t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			
			int xx=t.x+a[i][0];
			int yy=t.y+a[i][1];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&s[xx][yy]!='0'&& mk[xx][yy]==0)
			{
				mk[xx][yy]=1;
				q.push((node){xx,yy});
			}		}
	}
	return;
}

The main function ：

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]!='0' && mk[i][j]==0)
			{
				res++;
				mk[i][j]=1;
				bfs(i,j);
			}
		}
	} 
	cout<<res<<endl;
	return 0;
}

Complete code

#include<iostream>
#include<queue>
using namespace std;
int a[4][2]={
   {1,0},{-1,0},{0,1},{0,-1}};
int n,m,res=0;
char s[1000][1000];
int mk[1000][1000];
struct node{
	int x;
	int y;
};

void bfs(int x,int y)
{
	queue<node>q;
	q.push((node){x,y});
	while(q.size())
	{
		node t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			
			int xx=t.x+a[i][0];
			int yy=t.y+a[i][1];
			if(xx>=1 && xx<=n && yy>=1&& yy<=m && s[xx][yy]!='0'&& mk[xx][yy]==0)
			{
				mk[xx][yy]=1;
				q.push((node){xx,yy});
			}		}
	}
	return;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]!='0' && mk[i][j]==0)
			{
				res++;
				mk[i][j]=1;
				bfs(i,j);
			}
		}
	} 
	cout<<res<<endl;
	return 0;
}