救救孩子,dj无法编译
查看原帖
救救孩子,dj无法编译
714936
_lingrui楼主2023/10/27 17:22
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
vector<int> mp[100005];
int dis[1000005],minx,miny;
char mp0[1005][1005];
bool vis[1000005];
int n,sx,sy,ex,ey;
void dj(int sw,int ew){
	for(int i=1;i<=n;i++){
		minx=inf;
		for(int j=n;j<=n*n+n;j++){
			if(dis[j]<minx&&vis[j]==0){
				minx=dis[j];
				miny=j;
			}
		}
		vis[miny]=1;
		if(miny==ew){
			cout << minx;
			exit(0);
		}
		for(int i=0;i<mp[minx].size();i++){
			dis[mp[minx][i]]=min(dis[mp[minx][i]],minx+1);
		}
	}
}
int main(){
	cin >> n;
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
	        cin >> mp0[i][j];
			if(mp0[i][j]=='0'){
				mp0[i][j]='2';
			}
		}
	}
	cin >> sx >> sy >> ex >> ey;
	dis[(sx-1)*n+sy]=0;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(mp0[i][j]=='2'){
				int tmp;
				if(mp[i-1][j]=='2'){
					tmp=(i-1)*n+j-n;
					mp[(i-1)*n+j].push_back(tmp);
				}
				if(mp[i+1][j]=='2'){
					tmp=(i-1)*n+j+n;
					mp[(i-1)*n+j].push_back(tmp);
				}
				if(mp[i][j-1]=='2'){
					tmp=(i-1)*n+j-1;
					mp[(i-1)*n+j].push_back(tmp);
				}
				if(mp[i-1][j]=='2'){
					tmp=(i-1)*n+j+1;
					mp[(i-1)*n+j].push_back(tmp);
				}
			}
		}
	}
	dj((sx-1)*n+sy,(ex-1)*n+ey);
	return 0;
}
2023/10/27 17:22
加载中...