八十分求助
查看原帖
八十分求助
1115904
malinhao45楼主2024/9/17 12:01
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c=0,d=1,m;
vector<pair<int,int>>a[500000];
char s[5000][5000];
int dx[4]= {1,0,-1,0};
int dy[4]= {0,1,0,-1};
bool vis[9000000];
int dis[9000000];
void spfa(int x) {
	for(int i=0; i<n*m; i++) {
		dis[i]=1e18;
		vis[i]=false;
	}
	queue<int>q;
	q.push(x);
	dis[x]=0;
	vis[x]=true;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(auto v:a[u]) {
			if(dis[u]<1e11&&dis[v.first]>dis[u]+v.second) {
				dis[v.first]=dis[u]+v.second;
				if(!vis[v.first]) {
					vis[v.first]=true;
					q.push(v.first);
				}
			}
		}
	}
}
int x10=0,y10=0,x20,y20;
signed main() {
	while(cin>>n>>m) {
		if(!n&&!m) {
			break;
		}
		for(int i=0; i<n; i++) {
			a[i].clear();
			for(int j=0; j<m; j++) {
				cin>>s[i][j];
			}
		}
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				for(int k=0; k<4; k++) {
					int x=dx[k]+i;
					int y=dy[k]+j;
					if(!(x>=0&&x<=n&&y>=0&&y<=m)) {
						continue;
					}
					int t1=m*i+j;
					int t2=m*x+y;
					if(s[i][j]==s[x][y]) {
						a[t1].push_back({t2,c});
					} else {
						a[t1].push_back({t2,d});
					}
				}
			}
		}
		cin>>x10>>y10>>x20>>y20;
		spfa(x10*m+y10);
		cout<<dis[x20*m+y20]<<endl;
	}


}
2024/9/17 12:01
加载中...