求助01bfsRE或TLE
查看原帖
求助01bfsRE或TLE
467906
Anyakwi楼主2022/11/9 08:45

rt

#include<bits/stdc++.h>
using namespace std;

const int maxn=505;
int n,m,sx,sy,tx,ty;
int dis[maxn][maxn],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
char mp[maxn][maxn];

void bfs()
{
	deque<pair<int,int> >q;
	memset(dis,0x3f,sizeof dis);
	dis[sx][sy]=0;
	q.push_back(make_pair(sx,sy));
	while(!q.empty())
	{
		int x=q.front().first,y=q.front().second;q.pop_front();
		for(int i=0;i<4;i++)
		{
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m) continue;
			int c=(mp[x][y]!=mp[nx][ny]);
			if(dis[x][y]+c<dis[nx][ny])
			{
				dis[nx][ny]=dis[x][y]+c;
				if(c) q.push_back(make_pair(nx,ny));
				else q.push_front(make_pair(nx,ny));
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	while(true)
	{
		cin>>n>>m;
		if(n==0&&m==0) break;
		for(int i=1;i<=n;i++)
			scanf("%s",mp[i]+1);
		
		cin>>sx>>sy>>tx>>ty;
		sx++,sy++,tx++,ty++;
		
		bfs();
		cout<<dis[tx][ty]<<endl;
		
	}	
	return 0;
}

2022/11/9 08:45
加载中...