0分www
查看原帖
0分www
1160828
jiqihang楼主2024/12/5 19:43
#include<bits/stdc++.h>

#define fi first
#define sc second

using namespace std;

const int N=510;
typedef pair<int,int> PII;

int n,m;
char g[N][N];
deque<PII> q;
int dist[N][N];

int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

int bfs(int x,int y)
{
	int x1,x2,y1,y2;
	q.push_back({x,y});
	dist[x][y]=0;
	
	while(q.size())
	{
		auto t=q.front();
		q.pop_front();
		char ch=g[t.fi][t.sc];
		
		for(int i=0;i<4;i++)
		{
			int a=t.fi+dx[i],b=t.sc+dy[i];
			
			if(a<0||a>=n||b<0||b>=m) continue;
			if(dist[a][b]>=0) continue;
			
			if(g[a][b]==ch)
			{
				dist[a][b]=dist[t.fi][t.sc];
				q.push_front({a,b});
			}
			
			if(g[a][b]!=ch)
			{
				dist[a][b]=dist[t.fi][t.sc]+1;
				q.push_back({a,b});
			}
			
			if(a==x2&&b==y2) return dist[x2][y2];
		}
	}
	return -1;
}
int main()
{
	while(cin>>n>>m,n||m)
	{
        int x1,x2,y1,y2;
		for(int i=0;i<n;i++)
		{
			scanf("%s",g[i]);
		}
		memset(dist,-1,sizeof dist);
		q.clear();
		cin>>x1>>y1>>x2>>y2;
		int res=bfs(x1,y1);
		cout<<res<<endl;
	}
	return 0;
}
2024/12/5 19:43
加载中...