dfs悬赏膜拜!
查看原帖
dfs悬赏膜拜!
590571
_weishiqi66_楼主2022/12/15 13:58
#include<bits/stdc++.h>
#define yy yyyyyyyyyyyy
using namespace std;
int n,m;
int ox,oy,ans=1000000;
int a[305][305],wx[5]={0,1,-1,0,0},wy[5]={0,0,0,1,-1};

void bfs(int x,int y,int t){
	a[x][y]=1;
	for(int i=1;i<=n;i++){//调试语句 
		for(int j=1;j<=n;j++){
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
	if(x<1||y<1||x>n||y>m) return;
	if(x==ox&&y==oy){
		ans=min(ans,t);
		return;
	}
	if(a[x][y]==3){
		 for(int i=1;i<=n;i++){
			for(int j=1;i<=n;i++){
				if(a[i][j]==3){
					a[x][y]=1,a[i][j]=1;
					bfs(i,j,t);
					a[x][y]=3,a[i][j]=3;
				}
			}
		 }
	}
	
	for(int i=1;i<=4;i++){
		int xx=x+wx[i],yy=y+wy[i];
		if(a[xx][yy]!=1){
			int b=a[xx][yy];
			a[xx][yy]=1;
			bfs(xx,yy,t+1);
			a[xx][yy]=b;
		}		
	}
	return;
}
int main(){
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char b;
			cin>>b;
			if(b=='@') x=i,y=j;
			if(b=='=') ox=i,oy=j;
			if(b=='#') a[i][j]=1;
			if(b<='Z'&&b>='A') a[i][j]=3;
		}
	}
	bfs(x,y,1);
	cout<<ans;
	return 0;
}
2022/12/15 13:58
加载中...