WA234,40分求助!!
查看原帖
WA234,40分求助!!
1036281
mayisang楼主2023/10/17 21:28
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x_1,y_1,x_2,y_2,d[510][510],book[510][510];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char a[510][510];
struct lattice{int x,y,co;};
void SPFA(){
	memset(book,0,sizeof(book));
	d[x_1][y_1]=0;
	book[x_1][y_1]=1;
	queue<lattice>q;
	q.push(lattice{x_1,y_1,0});
	while(!q.empty()){
		lattice v=q.front();
		q.pop();
		if(v.x==x_2&&v.y==y_2){
			return;
		}
		book[v.x][v.y]=0;
		for(int i=0;i<4;i++){
			int tx=dx[i]+v.x;
			int ty=dy[i]+v.y;
			if(tx<1||tx>n||ty<1||ty>m){
				continue;
			}
			int cost=0;
			if(a[tx][ty]!=a[v.x][v.y]){
				cost=1;
			}
			if(d[tx][ty]>d[v.x][v.y]+cost){
				d[tx][ty]=d[v.x][v.y]+cost;
			//	cout<<"***********"<<tx<<"***"<<ty<<"***"<<d[tx][ty]<<endl;
				if(!book[tx][ty]){
					book[tx][ty]=1;
					q.push(lattice{tx,ty,d[tx][ty]});
				}
			}
		}
	}
	return;
}
signed main(){
	while(cin>>n>>m){
		if(m==0&&n==0){
			return 0;
		}
		memset(d,0x3f,sizeof(d));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		cin>>x_1>>y_1>>x_2>>y_2;
		x_1++,x_2++,y_1++,y_2++;
		SPFA();
		cout<<d[x_2][y_2]<<endl;
	}
	return 0;
}
2023/10/17 21:28
加载中...