WA#2求助
查看原帖
WA#2求助
1339558
silent_candle楼主2025/6/12 12:38
#include<bits/stdc++.h>
using namespace std;
struct e{
	int next,to,w;
}edge[5000055];
int n,m,cnt,x,y,x2,y2;
int d[250055],pd[250055],f[250055];
char a[885][885];
void cun(int u,int v,char x,char y)
{
	if(u<=0||v<=0||u>n*m||v>n*m)return;
	edge[++cnt].to=v;
	edge[cnt].next=f[u];
	f[u]=cnt;
	if(x==y)edge[cnt].w=0;
	if(x!=y)edge[cnt].w=1;
}
priority_queue <pair<int,int> > q;
void dij(int s)
{
	
	d[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty())
	{
		int t=q.top().second;
		q.pop();
		if(pd[t]==1)continue;
		pd[t]=1;
		for(int i=f[t];i;i=edge[i].next)
		{
			if(d[edge[i].to]>d[t]+edge[i].w)
			{
				d[edge[i].to]=d[t]+edge[i].w;
				q.push(make_pair(-d[edge[i].to],edge[i].to));
			}
		}
	}
}
int main()
{
	while(1)
	{
		memset(f,0,sizeof f);
		memset(edge,0,sizeof edge);
		memset(a,' ',sizeof a);
		memset(pd,0,sizeof pd);
		memset(d,0x7f,sizeof d);
		cnt=0;
		cin>>n>>m;
		if(!n&&!m)break;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		cin>>a[i][j];
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cun(i*m-m+j,i*m-m+j-1,a[i][j],a[i][j-1]);
				cun(i*m-m+j,i*m-m+j+1,a[i][j],a[i][j+1]);
				cun(i*m-m+j,i*m-m+j+m,a[i][j],a[i+1][j]);
				cun(i*m-m+j,i*m-m+j-m,a[i][j],a[i-1][j]);
			}
		}
		cin>>x>>y>>x2>>y2;
		dij(x*m+y+1);
		cout<<d[x2*m+y2+1]<<endl;
	}
	return 0;
}
2025/6/12 12:38
加载中...