【YBTOJ进阶训练指导】渡过河流【BFS】

思路：

我们可以一层一层BFS，每次把和当前所有相同的地形全部走到不能走，遇到不同的地形就判断是否要做竹筏。

#include
#include
#include

using namespace std;

int dx[8]={0, 1, 0, -1, 1, 1, -1, -1};
int dy[8]={1, 0, -1, 0, 1, -1, 1, -1};
struct code
{
	int x, y;
	code(int a=0, int b=0)
	{
		x=a;
		y=b;
	}
};
int n, k;
int ma[1010][1010], f[1010][1010], ans[1010][1010];
queue q, b;

void bfs(int x, int y)
{
	b.push(code(x, y));
	f[x][y]=2;
	while(!b.empty())
	{
		code u=b.front();
		b.pop();
		for(int i=0; i<8; i++)
		{
			int xx=u.x+dx[i], yy=u.y+dy[i];
			if(xx<0||xx>n+1||yy<0||yy>n+1)
				continue;
			if(ma[u.x][u.y]==ma[xx][yy])
			{
				if(f[xx][yy]==2)
					continue;
				f[xx][yy]=2;
				ans[xx][yy]=ans[u.x][u.y];
				b.push(code(xx, yy));
			}
			else
			{
				if(f[xx][yy])
					continue;
				f[xx][yy]=1;
				q.push(code(xx, yy));
			}
		}
	}
}

int main()
{
	scanf("%d%d", &n, &k);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			scanf("%1d", &ma[i][j]);
	q.push(code(0, 0));
	int last=0, sum=0;
	while(!q.empty())
	{
		code u=q.front();
		q.pop();
		if(f[u.x][u.y]==2)
			continue;
		if(ma[u.x][u.y]!=last&&ma[u.x][u.y])
			sum++;
		ans[u.x][u.y]=sum;
		bfs(u.x, u.y);
		last=ma[u.x][u.y];
	}
	for(int i=1; i<=k; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d ", ans[x][y]);
	}
	return 0;
}