18分求助
查看原帖
18分求助
220362
chenxuanting楼主2020/10/20 23:04
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
//typedef unsigned long long ll;
int n,m;
char a[305][305];
int mark[26];
struct node
{
	int x,y;
}b[26][2];
struct situ
{
	int x,y;
	int step;
};
int vis[305][305];
int stx,sty;
int ans;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void bfs()
{
	queue<situ> q;
	q.push((situ){stx,sty,0});
	while(!q.empty()){
		situ cur=q.front();
		q.pop();
		vis[cur.x][cur.y]=1;
		for(int i=0;i<4;i++){
			int x=cur.x+dx[i];
			int y=cur.y+dy[i];
			if(x<1||y<1||x>n||y>m){
				continue;
			}
			if(a[x][y]=='#'){
				continue;
			}
			if(vis[x][y]==1){
				continue;
			}
			if(a[x][y]>='A'&&a[x][y]<='Z'){
				if(x==b[a[x][y]-'A'][0].x&&y==b[a[x][y]-'A'][0].y){
					q.push((situ){b[a[x][y]-'A'][1].x,b[a[x][y]-'A'][1].y,cur.step+1});
				}else{
					q.push((situ){b[a[x][y]-'A'][0].x,b[a[x][y]-'A'][0].y,cur.step+1});
				}
			}
			if(a[x][y]=='='){
			    ans=cur.step+1;
			    return;
		    }
		    q.push((situ){x,y,cur.step+1});
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int i1=1;i1<=m;i1++){
			cin>>a[i][i1];
			if(a[i][i1]>='A'&&a[i][i1]<='Z'){
				b[a[i][i1]-'A'][mark[a[i][i1]-'A']].x=i;
				b[a[i][i1]-'A'][mark[a[i][i1]-'A']].y=i1;
				mark[a[i][i1]-'A']++;
			}
			if(a[i][i1]=='@'){
				stx=i;
				sty=i1;
			}
		}
	}
	for(int i=0;i<26;i++){
		if(mark[i]==1){
			mark[i]=0;
			a[b[i][0].x][b[i][0].y]='.';
		}
	}
	bfs();
	cout<<ans;
    return 0;
}
2020/10/20 23:04
加载中...