我拿dfs遍历的最多到5 有米有佬教下应该用啥算法
  • 板块P1443 马的遍历
  • 楼主A_xu
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/3/5 18:08
  • 上次更新2023/10/23 22:56:31
查看原帖
我拿dfs遍历的最多到5 有米有佬教下应该用啥算法
946604
A_xu楼主2023/3/5 18:08
#include <bits/stdc++.h>
using namespace std;

int n,m;

int minm;

int a[20][20];

int b[20][20];

void dfs(int bx,int by,int st,int ex,int ey){
	
	if(bx==ex&&by==ey){

		
		if(minm>st){
			
			minm=st;
			
			return;
			
		}
		
		return;
		
	}
	
	if(a[bx-2][by+1]==1&&b[bx-2][by+1]==0){
		b[bx-2][by+1]=1;
		dfs(bx-2,by+1,st+1,ex,ey);
		b[bx-2][by+1]=0;
		
	}//右上上 
	
	if(a[bx-1][by+2]==1&&b[bx-1][by+2]==0){
		b[bx-1][by+2]=1;
		dfs(bx-1,by+2,st+1,ex,ey);
		b[bx-1][by+2]=0;
	}//右右上 
	
	if(a[bx+1][by+2]==1&&b[bx+1][by+2]==0){
		b[bx+1][by+2]=1;
		dfs(bx+1,by+2,st+1,ex,ey);
		b[bx+1][by+2]=0;
	}//右右下 
	
	if(a[bx+2][by+1]==1&&b[bx+2][by+1]==0){
		b[bx+2][by+1]=1;
		dfs(bx+2,by+1,st+1,ex,ey);
		b[bx+2][by+1]=0;
		
	}//右下下 
	
	
	//e1
	if(a[bx+2][by-1]==1&&b[bx+2][by-1]==0){
		b[bx+2][by-1]=1;
		dfs(bx+2,by-1,st+1,ex,ey);
		b[bx+2][by-1]=0;
	}//左下下 
	
	if(a[bx+1][by-2]==1&&b[bx+1][by-2]==0){
		b[bx+1][by-2]=1;
		dfs(bx+1,by-2,st+1,ex,ey);
		b[bx+1][by-2]=0;
	}//左左下 
	
	if(a[bx-1][by-2]==1&&b[bx-1][by-2]==0){
		b[bx-1][by-2]=1;
		dfs(bx-1,by-2,st+1,ex,ey);
		b[bx-1][by-2]=0;
	}//左左上 
	
	if(a[bx-2][by-1]==1&&b[bx-2][by-1]==0){
		b[bx-2][by-1]=1;
		dfs(bx-2,by-1,st+1,ex,ey);
		b[bx-2][by-1]=0;
	}//右下下
	
}

int main(){
	int x,y;
	
	cin>>n>>m>>x>>y;
	for(int i = 1 ; i<=n ;i++){
		
		for(int j = 1 ; j<=m ;j++){
			
			a[i][j]=1;
			
		}
		
	}

	
	b[x][y]=1;
	
	for(int i = 1 ; i<=n ;i++){
		
		for(int j =1 ; j<=m ;j++){
		
				
				minm=9999;
				
			dfs(x,y,0,i,j);
			
			if(minm<9999){
				
			cout<<minm<<" ";	
				
			}else{
				
				cout<<"-1"<<" ";
			}
			
				
			
		}
		cout<<endl;
		
	}
	
	
}
2023/3/5 18:08
加载中...