???
查看原帖
???
558377
jixx楼主2023/7/8 12:30
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=301;
int n,m,sx,sy,tx,ty,vis[N][N],x1,x2,y1,y2;
int dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
struct node{
	int x,y,step;
};
char a[N][N];
queue<node> q;
int main(){
	scanf("%d %d",&n,&m);
	bool flag2=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@'){
				sx=i,sy=j;
			}else if(a[i][j]=='='){
				tx=i,ty=j;
			}else if(a[i][j]>='a'&&a[i][j]<='z'){
				if(flag2==1) x2=i,y2=j;
				else{
					x1=i,y1=j;
					flag2=1;
				}
			}
		}
	}
	//bfs
	node start;
	start.x=sx;
	start.y=sy;
	start.step=0;
	q.push(start);
	vis[sx][sy]=1;
	int flag=0;;
	while(!q.empty()){
		int idx=q.front().x,idy=q.front().y;
		if(idx==tx&&idy==ty){
			printf("%d",q.front().step);
			return 0;
		}
		for(int i=0;i<4;i++){
			int xx=idx+dx[i],yy=idy+dy[i];
			if(flag==1){
				int xx=x2+dx[i],yy=y2+dy[i];
				flag=0;
			}if(flag==2){
				int xx=x1+dy[i],yy=y1+dy[i];
				flag=0;
			} 
			if(xx<1||yy<1||xx>n||yy>m) continue;
			if(vis[xx][yy]==0&&a[xx][yy]!='#'){
				node temp;
				temp.x=xx;
				temp.y=yy;
				if(xx==x1&&yy==y1) flag=1;
				if(xx==x2&&yy==y2) flag=2;
				temp.step=q.front().step+1;
				q.push(temp);
				vis[xx][yy]=1;
			}
		}
		q.pop();
	}
	return 0;
}
新手,勿喷
2023/7/8 12:30
加载中...