求调玄关
查看原帖
求调玄关
745865
Emplace楼主2024/10/11 15:08
#include<bits/stdc++.h>
using namespace std;
int n,m,tx,ty,sx,sy,dis2[10][10]={{0,1},{1,0},{-1,0},{0,-1}};
char a[1000][1000];
int dis[500010],vis[500010],h[1000005],w2[1000005],e[1000005],ne[100005],idx;
void add(int a,int b,int t){
	w2[idx]=t,ne[idx]=h[a],e[idx]=b,h[a]=idx++;
}
bool check(int l){
	queue<int> p;
	p.push(l);
	vis[l]=1;
	for(int i=0;i<n*m;i++){
		dis[i]=0x3f3f3f3f;
	}
	dis[l]=0;
	while(!p.empty()){
		int x=p.front();
		p.pop();
		vis[x]=0;
		for(int i=h[x];~i;i=ne[i]){
			int v=e[i];
			int w=w2[i];
			if(dis[v]>dis[x]+w){
				dis[v]=dis[x]+w;
				if(vis[v]==0){
					vis[v]=1;
					p.push(v);
				}
			}
		}
	}
	return 1;
}
int main(){
	while(cin>>n>>m){
		idx=0;
		memset(h,-1,sizeof(h));
		if(n==0&&m==0){
			return 0;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>a[i][j];
			}
		}
		cin>>tx>>ty>>sx>>sy;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				for(int k=0;k<4;k++){
					int xx=i+dis2[k][0],yy=j+dis2[k][1];
					if(xx>=0&&yy>=0&&xx<n&&yy<m){
						if(a[i][j]==a[xx][yy]){
							add(i*m+j,xx*m+yy,0);
							add(xx*m+yy,i*m+j,0);
						}
						else{
							add(i*m+j,xx*m+yy,1);
							add(xx*m+yy,i*m+j,1);
						}
					}
				}
			}
		}
		memset(vis,0,sizeof(vis));
		memset(dis,0,sizeof(dis));
		check(tx*m+ty);
		cout<<dis[sx*m+sy]<<endl;
	}
	return 0;
}

wa4,5

2024/10/11 15:08
加载中...