60分有两个点RE,求大佬指点
查看原帖
60分有两个点RE,求大佬指点
778772
xsj4zyc楼主2024/8/30 21:21
#include<bits/stdc++.h>
using namespace std;
int n,m; 
char a[1000][1000];
int vist[1010][1010];
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
struct node{
	int x,y;
	int step;
}duile[1000000];
int ax,ay;
int bx,by;
void bfs(){
	int minn=INT_MAX;
	int l=1,r=0;
	duile[++r].x=ax;
	duile[r].y=ay;
	duile[r].step=0;
	vist[ax][ay]=0;
	while(l<=r){
		int nowx=duile[l].x;
		int nowy=duile[l].y;
		int nstep=duile[l].step;
		for(int i=0;i<4;i++){
			int nextx=nowx+dx[i];
			int nexty=nowy+dy[i];
			int nnstep;
			if(a[nowx][nowy]!=a[nextx][nexty]) nnstep=nstep+1;
			else nnstep=nstep;
			if(nextx>=0&&nextx<n&&nexty>=0&&nexty<m&&nnstep<vist[nextx][nexty]){
				duile[++r].x=nextx;
				duile[r].y=nexty;
				duile[r].step=nnstep;
				vist[nextx][nexty]=nnstep;
			}
		}
	//	cout<<nowx<<"   "<<nowy<<"   "<<vist[nowx][nowy]<<endl; 
		l++;
	}
	cout<<vist[bx][by]<<endl;
}
int main(){
	while(cin>>n>>m){
		for(int i=0;i<1010;i++){
			for(int j=0;j<1010;j++) vist[i][j]=INT_MAX;
		}
		string x[1000];
		if(n==0&&m==0){
			return 0;
		}
		for(int i=0;i<n;i++) cin>>x[i];
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				a[i][j]=x[i][j];
			}
		}
		cin>>ax>>ay>>bx>>by;
		bfs();
	}
	return 0;
}
2024/8/30 21:21
加载中...