bfs40分求助
查看原帖
bfs40分求助
472714
hanjunhao楼主2021/11/23 12:18
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
char map[10000][10000];
int vis[10000][10000];
int m, n;
int sum;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
queue <int> q;
void bfs(int x, int y)
{
	if (vis[x][y] == 1)
		return;
	vis[x][y] = 1;
	q.push(x);
	q.push(y);
	while (!q.empty())
	{
		//cout << 1 << endl;
		int nn = q.front();
		q.pop();
		int mm = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			nn += dx[i];
			mm += dy[i];
			if (map[nn][mm] == '0' || vis[nn][mm] == 1||nn<=0||nn>m||mm<=0||mm>n)
				continue;
			vis[nn][mm] = 1;
			q.push(nn);
			q.push(mm);
		}
	}
}
int main()
{
	cin >> m >> n;
	for (int i = 1; i <= m; i++)
	{ 
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
		}
	}
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{	//cout << 2 << endl;
			if (vis[i][j] != 1 && map[i][j] != '0')
			{
				cout << i << j << endl;
				sum++;
				bfs(i, j);
			}
		}
	}
	cout << sum << endl;
}
2021/11/23 12:18
加载中...