求大佬帮看看QAQ
查看原帖
求大佬帮看看QAQ
258694
PP00544楼主2021/12/19 20:49
#include <bits/stdc++.h> 
using namespace std; 
const int MAXN=1000+10; 
int w,h; 
const int dx[4]={-1,0,1,0}; 
const int dy[4]={0,1,0,-1}; 
int mp[MAXN][MAXN]; 
int A[MAXN][MAXN]; 
int B[MAXN][MAXN]; 
int mp1[MAXN][MAXN]; 
int bgx,bgy,edx,edy; 
bool f[MAXN][MAXN]; 
bool flag; 
void bfs(int a,int b){ 
	queue<int> x; 
	queue<int> y; 
	x.push(a); 
	y.push(b); 
	while(!x.empty()){ 
		int X=x.front();x.pop(); 
		int Y=y.front();y.pop(); 
		for(int i=0;i<4;i++){ 
			int nx=X+dx[i]; 
			int ny=Y+dy[i]; 
			if(nx<0 || nx>h || ny<0 || ny>w || f[nx][ny]==true || mp[nx][ny]==1 || (flag==false && nx==edx && ny==edy)){ 
				continue; 
			} 
			mp1[nx][ny]=min(mp1[X][Y]+1,mp1[nx][ny]); 
			x.push(nx); 
			y.push(ny); 
			f[nx][ny]=true; 
		} 
	} 
} 
int main(){ 
	cin>>w>>h; 
	memset(mp1,0x3f,sizeof(mp1)); 
	for(int i=0;i<h;i++){ 
		for(int j=0;j<w;j++){ 
			cin>>mp[i][j]; 
			if(mp[i][j]==2){ 
				bgx=i; 
				bgy=j; 
			} 
			if(mp[i][j]==3){ 
				edx=i; 
				edy=j; 
			} 
		} 
	} 
	mp1[bgx][bgy]=0; 
	bfs(bgx,bgy); 
	flag=true; 
	for(int i=0;i<h;i++){ 
		for(int j=0;j<w;j++){ 
			A[i][j]=mp1[i][j]; 
			/*if(mp1[i][j]>100000){ 
				cout<<"INF"<<" "; 
			} 
			else cout<<mp1[i][j]<<" "; 
		} 
		cout<<endl;*/ 
		} 
	} 
	memset(mp1,0x3f,sizeof(mp1)); 
	memset(f,0,sizeof(f)); 
	mp1[edx][edy]=0; 
	bfs(edx,edy); 
	//cout<<endl; 
	int minn=0x3f3f3f3f; 
	/*for(int i=0;i<h;i++){ 
		for(int j=0;j<w;j++){ 
			//A[i][j]=mp1[i][j]; 
			if(mp1[i][j]>100000){ 
				cout<<"INF"<<" "; 
			} 
			else cout<<mp1[i][j]<<" "; 
		} 
		cout<<endl; 
	}*/  
	for(int i=0;i<h;i++){ 
		for(int j=0;j<w;j++){ 
			if(mp[i][j]==4) 
				minn=min(minn,mp1[i][j]+A[i][j]); 
		} 
	} 
	cout<<minn<<endl; 
	return 0;	
}


2021/12/19 20:49
加载中...