80分wa on#2求助
查看原帖
80分wa on#2求助
760776
zzy_zzy楼主2023/9/21 12:06

RT.

#include<bits/stdc++.h>
using namespace std;
int a[510][510],dis[510][510],vis[510][510],n,m;
int dx[5]={1,-1,0,0},dy[5]={0,0,-1,1};
void bfs(int ksx,int ksy){
	deque<pair<int,int> >q;
	dis[ksx][ksy]=0;
	q.push_front(make_pair(ksx,ksy));
	while(q.size()){
		int x=q.front().first,y=q.front().second;
		q.pop_front();
		if(vis[x][y]){
			continue;
		}
		vis[x][y]=1;
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>n||xx<1||yy>m||xx<1||vis[xx][yy]){
				continue;
			}
			bool b=0;
			if(a[x][y]!=a[xx][yy]){
				b=1;
			}
			if(dis[xx][yy]>dis[x][y]+b){
				dis[xx][yy]=dis[x][y]+b;
				if(b){
					q.push_back(make_pair(xx,yy));
				}
				else{
					q.push_front(make_pair(xx,yy));
				}
			}
		}
	}
}

int main(){
	while(cin>>n>>m&&n&&m){
		memset(a,0,sizeof(a));
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char ch;
//				while(ch!='#'&&ch!='@'){
				cin>>ch;
//				}
				if(ch=='#'){
					a[i][j]=0;
				}
				else{
					a[i][j]=1;
				}
			}
//			getchar();
		}
		int ksx,ksy,jsx,jsy;
		cin>>ksx>>ksy>>jsx>>jsy;
		ksx++,ksy++,jsx++,jsy++;
		bfs(ksx,ksy);
		cout<<dis[jsx][jsy]<<endl;
	}
	return 0;
}
2023/9/21 12:06
加载中...