求助
查看原帖
求助
556362
Unnamed114514楼主2022/2/25 23:45
#include<bits/stdc++.h>
#define Maxn 1000005
#define ll long long
using namespace std;
int n,m,a=2e9,sx,sy,lx,ly,ans[305][305],x[30][10],y[30][10];
char s[305][305];
void dfs(int xx,int yy,int t,bool p){
	if(xx<1||xx>n||yy<1||yy>n||s[xx][yy]=='#'||t>=a)
		return;
	if(xx==lx&&yy==ly){
		a=t;
		return;
	}
	if(ans[xx][yy]!=-1&&t>=ans[xx][yy])
		return;
	ans[xx][yy]=t;
	if(isupper(s[xx][yy])){
		int k=s[xx][yy]-'A';
		if(p){
			if(x[k][1]==xx&&y[k][1]==yy)
				dfs(x[k][2],y[k][2],t,0);
			else
				dfs(x[k][1],y[k][1],t,0);
			return;
		}
	}
	dfs(xx-1,yy,t+1,1);
	dfs(xx+1,yy,t+1,1);
	dfs(xx,yy+1,t+1,1);
	dfs(xx,yy-1,t+1,1);
}
int main(){
	scanf("%d %d\n",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans[i][j]=-1;
			s[i][j]=getchar();
			if(s[i][j]=='@')
				sx=i,sy=j;
			else if(s[i][j]=='=')
				lx=i,ly=j;
			else if(isupper(s[i][j])){
				int k=s[i][j]-'A';
				if(y[k][1])
					x[k][2]=i,y[k][2]=j;
				else
					x[k][1]=i,y[k][1]=j;
			}
		}
		getchar();
	}
	dfs(sx,sy,0,1);
	printf("%d\n",a);
	return 0;
}
2022/2/25 23:45
加载中...