P1141 01迷宫 题解

题目传送门

题目描述

有一个仅由数字 0 与 1 组成的 n × n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入格式

第一行为两个正整数 n,m。

下面 n 行，每行 n 个字符，字符只可能是 0 或者 1，字符之间没有空格。

接下来 m 行，每行两个用空格分隔的正整数 i,j，对应了迷宫中第 i 行第 j 列的一个格子，询问从这一格开始能移动到多少格。

输出格式

m 行，对于每个询问输出相应答案。

输入输出样例 #1

输入 #1

 2 2
 01
 10
 1 1
 2 2
 

输出 #1

 4
 4
 

说明/提示

对于样例，所有格子互相可达。

• 对于 20% 的数据，n ≤ 10；
• 对于 40% 的数据，n ≤ 50；
• 对于 50% 的数据，m ≤ 5；
• 对于 60% 的数据，n,m ≤ 100；
• 对于 100% 的数据，1 ≤ n ≤ 1000，1 ≤ m ≤ 100000。

#include<iostream>
 #include<queue>
 using namespace std;
 int n, m;
 const int MAXN = 1024;
 char matrix[MAXN][MAXN];
 int max_connected[MAXN][MAXN];
 int bkt[MAXN*MAXN];
 const int xo[] = { -1,0,+1,0 };
 const int yo[] = { 0,+1,0,-1 };
 int mccount = 1;//max connected count
 struct pos
 {
 	int x;
 	int y;
 };
 void bfs(int x, int y, int color)
 {
 	queue<pos> que;
 	que.push({ x,y });
 	max_connected[x][y] = color;
 	while (!que.empty())
 	{
 		pos this_pos = que.front();
 		que.pop();
 		for (int i = 0; i < 4; i++)
 		{
 			int nx = this_pos.x + xo[i];
 			int ny = this_pos.y + yo[i];
 			if (max_connected[nx][ny] != 0) continue;
 			if (matrix[nx][ny] == matrix[this_pos.x][this_pos.y]) continue;
 			if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
 			max_connected[nx][ny] = color;
 			que.push({ nx,ny });
 		}
 	}
 }
 int main()
 {
 	cin >> n >> m;
 	for (int i = 1; i <= n; i++) 
 	{
 		for (int j = 1; j <= n; j++) 
 		{
 			cin >> matrix[i][j];
 		}
 	}
 	for (int i = 1; i <= n; i++)
 	{
 		for (int j = 1; j <= n; j++)
 		{
 			if (max_connected[i][j] == 0)
 			{
 				bfs(i, j, mccount);
 				mccount++;
 			}
 		}
 	}
 	for (int i = 1; i <= n; i++)
 	{
 		for (int j = 1; j <= n; j++)
 		{
 			bkt[max_connected[i][j]]++;
 		}
 	}
 	for (int i = 1; i <= m; i++)
 	{
 		int x, y;
 		cin >> x >> y;
 		cout << bkt[max_connected[x][y]] << endl;
 	}
 	return 0;
 }
 

总结

输入char二维数组时，尽量不要直接

for (int i = 1; i <= n; i++) 
 	{
 		cin >> matrix[i];
 	}
 

这样会导致下标是从0开始的，也会导致最后多一个"\0"，以后尽量不要用这种写法