急切需要大佬的帮助!!!
查看原帖
急切需要大佬的帮助!!!
800751
acmwriter楼主2023/6/13 22:07
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char a[305][305];
int b[305][305];
int n,m,nx,ny,fx,fy,sum=90000000;
int ax[26],bx[26],ay[26],by[26];
int dfs(int x,int y,int t){
	if(x==fx&&y==fy){
		sum=min(sum,t);
		return 0;
	}
	for(int i=0;i<4;i++){
		int sx=x+dx[i];
		int sy=y+dy[i];
		if(sx>=1&&sx<=n&&sy>=1&&sy<=m&&a[sx][sy]=='.'&&b[sx][sy]==0){
			b[sx][sy]=1;
			t++;
			dfs(sx,sy,t);
			b[sx][sy]=0;
		}
		if(sx>=1&&sx<=n&&sy>=1&&sy<=m&&a[sx][sy]>='A'&&a[sx][sy]<='Z'&&b[sx][sy]==0){
			b[sx][sy]=1;
			t++;
			if(ax[a[sx][sy]-'A']==sx&&ay[a[sx][sy]-'A']==sy)dfs(bx[a[sx][sy]-'A'],by[a[sx][sy]-'A'],t);
			if(bx[a[sx][sy]-'A']==sx&&by[a[sx][sy]-'A']==sy)dfs(ax[a[sx][sy]-'A'],ay[a[sx][sy]-'A'],t);
			b[sx][sy]=0;
		}
    }
}
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]=='@'){
			   nx=i;
			   ny=j;
		    }
		    if(a[i][j]=='='){
			   fx=i;
			   fy=j;
			}
			if(a[i][j]>='A'&&a[i][j]<='Z'){
				if(ax[a[i][j]-'A']==0&&ay[a[i][j]-'A']==0)
				ax[a[i][j]-'A']=i,ay[a[i][j]-'A']=j;
				if(ax[a[i][j]-'A']!=0&&ay[a[i][j]-'A']!=0)
				bx[a[i][j]-'A']=i,by[a[i][j]-'A']=j;
			}
		}
	}
	dfs(nx,ny,0);
	cout<<sum;
	return 0;
}
2023/6/13 22:07
加载中...