01bfs(双端队列bfs) 20pts 求助
查看原帖
01bfs(双端队列bfs) 20pts 求助
807853
I_am_AKed_by_NOI楼主2023/3/1 20:15
#include<bits/stdc++.h>
using namespace std;
const int N=510;
char a[N][N];
int dis[N][N];
bool vis[N][N];
int n,m,s1,s2,e2,e1;
struct node
{
	int x,y;
};
deque<node> q;
int dx[4]={0,1,0,-1},
	dy[4]={1,0,-1,0};
int main()
{
	while(cin>>n>>m && n && m)
	{
		q.clear();
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>a[i][j];
			}
		}
		cin>>s1>>s2>>e1>>e2;
		dis[s1][s2]=0;
		q.push_back({s1,s2});
		while(!q.empty())
		{
			node tmp=q.front();
			q.pop_front();
			if(vis[tmp.x][tmp.y])
			{
				continue;
			} 
			vis[tmp.x][tmp.y]=1;
			if(e1==tmp.x && e2==tmp.y)
			{
				cout<<dis[tmp.x][tmp.y]<<endl;
				break;
			}
			for(int i=0;i<4;i++)
			{
				int xx=tmp.x+dx[i];
				int yy=tmp.y+dy[i];
				int v=(a[xx][yy]!=a[tmp.x][tmp.y]);
				if(xx>0 && yy>0 && xx<=n && yy<=m && dis[tmp.x][tmp.y]+v<dis[xx][yy])
				{
					dis[xx][yy]=dis[tmp.x][tmp.y]+v;
					if(v==0)
					{
						q.push_front({xx,yy});
					}
					else
						q.push_back({xx,yy});
				}
			}
		}
	}
	return 0;
}

rt

2023/3/1 20:15
加载中...