[ybtoj advanced training guidance] cross the river [BFS]

Ideas ：

We can layer by layer BFS, Every time you walk all the same terrain as the current one, you can't walk , If you encounter different terrain, you can judge whether to make a bamboo raft .

$code$

#include<iostream>
#include<cstdio>
#include<queue>

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<code> 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;
}