dfs求大佬们调试
查看原帖
dfs求大佬们调试
1389641
_Kenba_楼主2024/12/9 16:06
#include<bits/stdc++.h>
using namespace std;
int r,c;
char h[55][55];
int v[55][55];
int x,y;
int flag1,flag2,flag3,flag4;
int mx,my,mnx=1000,mny=1000;
int dx[8]={0,0,-1,1,-1,1,-1,1};
int dy[8]={1,-1,0,0,1,1,-1,-1};
int ans=10000;
void dfs(int sx,int sy,int step){
	
	for(int i=0;i<8;i++){
		int nx=sx+dx[i];
		int ny=sy+dy[i];
		if(h[sx][sy]=='*'&&step!=0&&flag1==1&&flag2==1&&flag3==1&&flag4==1){
		ans=min(ans,step);
		return;
	}
		if(nx>=1&&ny>=1&&nx<=r&&ny<=c&&v[nx][ny]==0&&h[nx][ny]!='X'){
			v[nx][ny]=1;
			if(nx>mx||nx<mnx||ny>my||ny<mny){
				if(nx>mx){
					if(flag1==1){
						dfs(nx,ny,step+1);
						v[nx][ny]=0;
					}
					if(flag1==0){
						flag1=1;
						dfs(nx,ny,step+1);
						v[nx][ny]=0;
						flag1=0;
					}
				}
				if(nx<mnx){
					if(flag2==1){
						dfs(nx,ny,step+1);
						v[nx][ny]=0;
					}
					if(flag2==0){
						flag2=1;
						dfs(nx,ny,step+1);
						v[nx][ny]=0;
						flag2=0;
					}
				}
				if(ny>my){
					if(flag3==1){
						dfs(nx,ny,step+1);
						v[nx][ny]=0;
					}
					if(flag3==0){
						flag3=1;
						dfs(nx,ny,step+1);
						v[nx][ny]=0;
						flag3=0;
					}
				}
				if(ny<mny){
					if(flag3==1){
						dfs(nx,ny,step+1);
						v[nx][ny]=0;
					}
					if(flag3==0){
						flag3=1;
						dfs(nx,ny,step+1);
						v[nx][ny]=0;
						flag3=0;
					}
				}
			}
			else{
			dfs(nx,ny,step+1);
			v[nx][ny]=0;
			}
		}
	}
}
int main(){
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>h[i][j];
			if(h[i][j]=='*'){
				x=i;
				y=j;
			}
			if(h[i][j]=='X'){
				mx=max(mx,i);
				my=max(my,j);
				mnx=min(mnx,i);
				mny=min(mny,j);
			}
		}
	}
	dfs(x,y,0);
	cout<<ans;
	return 0;
}
2024/12/9 16:06
加载中...