46求助
查看原帖
46求助
169736
Fu_Tao楼主2022/5/25 21:15
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
ll n,m,sx,sy,ex,ey,head=1,tail=2,nx,ny,book[1001][1001];
char a[3001][3001];
const ll near[8][2]={{0,1},{1,0},{0,-1},{-1,0}};
struct node{
	ll x,y,t;
}que[1000001];
void finds(char c,ll u,ll v){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==c&&u!=i&&v!=j){
				nx=i,ny=j;
				return ;
			}
		}
	}
	return ;
}
void bfs(){
	while(head<tail){
		if(que[head].x==ex&&que[head].y==ey)break;
		for(int i=0;i<4;i++){
			ll dx=que[head].x+near[i][0];
			ll dy=que[head].y+near[i][1];
			if(a[dx][dy]>='A'&&a[dx][dy]<='Z'){
				finds(a[dx][dy],dx,dy);
				dx=nx;dy=ny;
			}
			if(a[dx][dy]=='#'||dx>n||dx<1||dy>m||dy<1||book[dx][dy]==1)continue;
			book[dx][dy]=1;
			que[tail].x=dx;
			que[tail].y=dy;
			que[tail].t=que[head].t+1;
			tail++;
		}
		head++;
	}
	return ;
}
int main(){
	cin>>n>>m;
	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]=='=')ex=i,ey=j;
		}
	}
	que[head].x=sx,que[head].y=sy,que[head].t=0;
	book[sx][sy]=1;
	bfs();
	cout<<que[head].t;
	return 0;
} 
2022/5/25 21:15
加载中...