dij求助
  • 板块P4554 小明的游戏
  • 楼主_JF_殉情
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/4/13 21:24
  • 上次更新2023/10/28 03:48:19
查看原帖
dij求助
361141
_JF_殉情楼主2022/4/13 21:24
#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
char s[700][700];
int x[700][700],a[700][700];
int visit[N],d[N];
void dijkstra(int x,int n)
{
	memset(d,0,sizeof(d));
	memset(visit,0,sizeof(visit));
	int Min,p;
	for(int i=1;i<=n;i++)
	{
		d[i]=a[x][i];
	}
	visit[x]=1;
	d[x]=0;
	for(int i=1;i<n;i++)
	{
		Min=1e18;
		for(int j=1;j<=n;j++)
		{
			if(!visit[j]&&Min>d[j])
			{
				p=j;
				Min=d[j];
			}
		}
		visit[p]=1;
		for(int j=1;j<=n;j++)
		{
			if(!visit[j]&&Min+a[p][j]<d[j])
				d[j]=Min+a[p][j];
		}
	}
}
int main()
{
	int n,m;
	while(cin>>n>>m&&n+m)
	{
		memset(x,0,sizeof(x));
		memset(a,1,sizeof(a));
		int now=0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				now++;
				cin>>s[i][j];
				x[i][j]=now;
			}
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(s[i][j]==s[i+1][j])
				{
					a[x[i][j]][x[i+1][j]]=0;
					a[x[i+1][j]][x[i][j]]=0;
				}
				if(s[i][j]==s[i][j+1])
				{
					a[x[i][j]][x[i][j+1]]=0;	
					a[x[i][j+1]][x[i][j]]=0;
				}
			}
		}
		int X1,X2,Y1,Y2;
		cin>>X1>>X2>>Y1>>Y2;
		int s=x[X1][X2],t=x[Y1][Y2];
		dijkstra(s,now);
		cout<<d[t]<<endl;
	}
	return 0;
}
2022/4/13 21:24
加载中...