马的遍历.txt

中过科学技术大学历年复试机试题

#include<stdio.h>
#include<stdlib.h>
#define N  6

 int a[N][N];
 int resolution=0; 
 
 void  print(){
    int i,j; 
	
	resolution++;//增加一种解
	
	printf("***********%d**************\n",resolution);
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
		   printf("%2d ",a[i][j]);
		
		}
		printf("\n");

	}
    printf("*************************************\n");
    
 }



void dfs(int x,int y,int count){
	 
   int tx,ty; 
   if(count>N*N){
	   system("pause");
       print();
       return; 
   }
   //下一跳
   if(y<N-1){tx=x;ty=y+1;//向右
            if(a[tx][ty]==0){
			         a[tx][ty]=count;
				     dfs(tx,ty,count+1);
			    	 a[tx][ty]=0;
                     //count--;
		   }
   }
   if(y<N-1&&x<N-1){tx=x+1;ty=y+1;//向右下角
            if(a[tx][ty]==0){
	                 a[tx][ty]=count;
					 dfs(tx,ty,count+1);
				     a[tx][ty]=0;
					 //count--;
			}
   }
   if(x<N-1){tx=x+1;ty=y;//向下
           if(a[tx][ty]==0){
			         a[tx][ty]=count;
			         dfs(tx,ty,count+1);
		             a[tx][ty]=0;
					 //count--;
		   }
   }

   if(y>0&&y<N-1&&x>0&&x<N-1){tx=x+1;ty=y-1;//向左下角
           if(a[tx][ty]==0){
	                a[tx][ty]=count;
	                dfs(tx,ty,count+1);  
		            a[tx][ty]=0;
					//count--;
		   }		
   }

   if(y>0){tx=x;ty=y-1;//向左
          if(a[tx][ty]==0){ 
	                a[tx][ty]=count;
					dfs(tx,ty,count+1);
                    a[tx][ty]=0;
					//count--;
		  }
   }
   if(x>0&&y>0){tx=x-1;ty=y-1;//向左上角
          if(a[tx][ty]==0){ 
			        a[tx][ty]=count;
				    dfs(tx,ty,count+1);
                    a[tx][ty]=0;
					//count--;
		  
		  }
   }
   if(x>0){tx=x-1;ty=y;//向上
          if(a[tx][ty]==0){
			       a[tx][ty]=count;
				   dfs(tx,ty,count+1);			
                   a[tx][ty]=0;
				   //count--;
		  }
   }
   if(x>0&&y<N-1){tx=x-1;ty=y+1;//向右上角
          if(a[tx][ty]==0){
			       a[tx][ty]=count;
				   dfs(tx,ty,count+1);
                   a[tx][ty]=0;
				   //count--;
		  }
   }
   
   //count++;
 } 
 
 
 main(){
  int i,j;
  int x,y;//(x,y)为出发点座标
  
  for(i=0;i<N;i++){//初始化棋盘
	  for(j=0;j<N;j++){
		  a[i][j]=0;
      }
  }
  
  printf("input x(0<X<8),y(0<X<8)\n");
  scanf("%d%d",&x,&y);
  a[x][y]=1;
  dfs(x,y,2);
}



/*
   for(i=0;i<8;++i){ 
     tx=hn[i].x;//hn[]保存八个方位子结点 
     ty=hn[i].y; 
     s[tx][ty]=count; 
     dfs(tx,ty,count+1);//递归调用 
     s[tx][ty]=0; 
   } 
   */