0分#求助#QAQ
查看原帖
0分#求助#QAQ
1273525
Danielhaohao楼主2024/8/30 09:50
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,ci;
};
struct ch{
	int x1,y1,x2,y2,cnt=0;
};
ch c[30];
char s[310][310];
bool flag[310][310];
int ans=0x3f3f3f3f;
int d[4][2]={-1,0,0,1,1,0,0,-1};
int n,m;
queue<node>q;
void bfs(int h,int l){
	node e;e.x=h;e.y=l;e.ci=0;
	q.push(e);
	while(!q.empty()){
		node e=q.front();q.pop();
		for(int i=0;i<=3;i++){
			int dx=e.x+d[i][0];
			int dy=e.y+d[i][1];
			if(dx<1||dx>n||dy<1||dy>m) continue;
			if(flag[dx][dy]==1) continue;
			if(s[dx][dy]=='#') continue;
			if(s[dx][dy]=='.'){
				flag[dx][dy]=1;
				node k;
				k.x=dx;
				k.y=dy;
				k.ci=e.ci+1;
				q.push(k);
			}
			if(s[dx][dy]>='A'&&s[dx][dy]<='Z'){
				int id=s[dx][dy]-'A';
				node k;
				if(c[id].x1==dx&&c[id].y1==dy){
					k.x=c[id].x2;
					k.y=c[id].y2;
				}
				else{
					k.x=c[id].x2;
					k.y=c[id].y2;
				}
				k.ci=e.ci+1;
				flag[k.x][k.y]=1;
				q.push(k);
			}
			if(s[dx][dy]=='='){
				if(e.ci +1<ans){
					ans=e.ci;
				}
			}
		}
	}
}
int main(){
	cin>>n>>m;
	int a,b;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>s[i][j];
			if(s[i][j]=='@'){
				a=i;b=j;
			}
			if(s[i][j]>='A'&&s[i][j]<='Z'){
				int id=s[i][j]-'A';
				if(c[id].cnt==0){
					c[id].x1=i;
					c[id].y1=j;
					c[id].cnt++;
				}
				else{
					c[id].x2=i;
					c[id].y2=j;
				}
			}
		}
    }
    bfs(a,b);
    cout<<ans;
    return 0;
}
2024/8/30 09:50
加载中...