题目

提交记录

#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n,m,v[1001][1001],a1,a2;
char a[1001][1001];
struct S{
	int x,y;
	int step;
}s1;
queue<S>q;
int cheak(int i,int j)
{
	if(!(i>0&&j>0&&i<=n&&j<=n))return 0;
	if(a[s1.x][s1.y]!=a[i][j])return 1;
}
void bfs()
{
	while(!q.empty())q.pop();
	memset(v,0,sizeof(v));
	//v[a1][a2]=1;
	q.push({a1,a2,1});
	while(!q.empty())
	{
		 s1=q.front();
		 q.pop();
		 if(s1.step==n*n)
		 {
		   cout<<s1.step<<"\n";
		   return;
		 }
		 for(int i=0;i<4;i++)
		    if(cheak(s1.x+dx[i],s1.y+dy[i])==1)
		    {
		      //v[s1.x+dx[i]][s1.y+dy[i]]=1;
			  q.push({s1.x+dx[i],s1.y+dy[i],s1.step+1});
			  //cout<<s1.x+dx[i]<<' '<<s1.y+dy[i]<<" "<<s1.step+1<<"\n";
		    }
	}
	cout<<s1.step<<"\n";
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
	while(m--)
	{
	     cin>>a1>>a2;
 	     bfs();
	}
	return 0;
}