19分求调
查看原帖
19分求调
586768
User586768楼主2023/8/8 22:08
#include <bits/stdc++.h>
using namespace std;
int m,n,sy,sx,ex,ey;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
char c[400][400];
int vis[400][400];
void bfs(int y,int x){
	queue<pair<pair<int,int>,int> > q;
	q.push(make_pair(make_pair(y,x),0));
	vis[y][x]=1;
	while(!q.empty()){
		pair<pair<int,int>,int> p=q.front();
		q.pop();
		if(p.first.first==ey&&p.first.second==ex){
			cout<<p.second;
			exit(0);
		}
		char ch=c[p.first.first][p.first.second];
		if(ch>='A'&&ch<='Z'){
			for(int i=0;i<n;i++){
				for(int j=0;j<m;j++){
					if(c[i][j]==ch&&i!=p.first.first&&j!=p.first.second){
						p.first.first=i;
						p.first.second=j;
					}
				}
			}
		}
		for(int i=0;i<4;i++){
			int xx=p.first.second+dx[i];
			int yy=p.first.first+dy[i];
			if(xx>=0&&xx<m&&yy>=0&&yy<n&&c[yy][xx]!='#'&&vis[yy][xx]==0){
				vis[yy][xx]=1;
				q.push(make_pair(make_pair(yy,xx),p.second+1));
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>c[i][j];
			if(c[i][j]=='@'){
				sy=i;
				sx=j;
			}
			if(c[i][j]=='='){
				ex=j;
				ey=i;
			}
		}
	}
	bfs(sy,sx);
	return 0;
} 
2023/8/8 22:08
加载中...