真奇怪
查看原帖
真奇怪
295367
djwj223楼主2022/1/19 21:02
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int M=505;
int n,m,dis[2][M][M],ans,a1,a2,b1,b2;
int x[]={0,1,-1,0,0},y[]={0,0,0,1,-1};
bool vis[2][M][M];
int main(){
	scanf("%d%d",&n,&m);
	while(n){
		memset(vis,0,sizeof(vis));
		memset(dis,0x7f,sizeof(dis));
		char s[M][M];
//		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%s",s[i]+1);
		scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
		if(a1==a2 && b1==b2){
			printf("0\n");
			continue;
		}
		a1++,a2++,b1++,b2++;
		dis[0][a1][b1]=dis[1][a2][b2]=0;
		deque<pair<int,int> > dq1,dq2;
		dq1.push_front(mp(a1,b1));
		dq2.push_front(mp(a2,b2));
		bool ok=1;
		while(ok){
			pair<int,int> now1=dq1.front();
			pair<int,int> now2=dq2.front();
			dq1.pop_front(),dq2.pop_front();
			vis[0][now1.fi][now1.se]=1;
			vis[1][now2.fi][now2.se]=1;
			for(int i=1;i<=4;i++){
				int na=now1.fi+x[i],nb=now1.se+y[i];
				if(na>0 && nb>0 && na<=n && nb<=m && !vis[0][na][nb]){
					if(s[na][nb]!=s[now1.fi][now1.se]){
						dis[0][na][nb]=dis[0][now1.fi][now1.se]+1;
						if(vis[1][na][nb]){
							ans=dis[0][na][nb]+dis[1][na][nb];
							ok=0; break;
						}
						dq1.push_back(mp(na,nb));
					}else{
						dis[0][na][nb]=dis[0][now1.fi][now1.se];
						if(vis[1][na][nb]){
							ans=dis[0][na][nb]+dis[1][na][nb];
							ok=0; break;
						}
						dq1.push_front(mp(na,nb));
					}
				}
			}
			if(!ok) break;
			for(int i=1;i<=4;i++){
				int na=now2.fi+x[i],nb=now2.se+y[i];
				if(na>0 && nb>0 && na<=n && nb<=m && !vis[1][na][nb]){
					if(s[na][nb]!=s[now2.fi][now2.se]){
						dis[1][na][nb]=dis[1][now2.fi][now2.se]+1;
						if(vis[0][na][nb]){
							ans=dis[0][na][nb]+dis[1][na][nb];
							ok=0; break;
						}
						dq2.push_back(mp(na,nb));
					}else{
						dis[1][na][nb]=dis[1][now2.fi][now2.se];
						if(vis[0][na][nb]){
							ans=dis[0][na][nb]+dis[1][na][nb];
							ok=0; break;
						}
						dq2.push_front(mp(na,nb));
					}
				}
			}
		}
		printf("%d\n",ans);
		scanf("%d%d",&n,&m);
	}
	return 0;
}

第一遍交的时候第十六行没加注释为什么也能过?

2022/1/19 21:02
加载中...