图的遍历算法-马遍历棋盘

红太狼 2022-08-23 09:56 192阅读 0赞

题目  
  
在n\*m的棋盘中，马只能走日子，马从位置（x,y）处出发，把棋盘的每一点都走一次，且只走一次，找出所有的路径。  
  
demo实现  
  
棋盘设置为5\*4，初始位置设置为(0.0)  
  
算法重点  
  
回溯  
  
在递归后方将坐标置为初始状态0。   
当路径错误的时候，能够把路径恢复到走之前的状态。

具体的实现(java代码)

package test;

/\*\*  
 \* 在n\*m的棋盘中，马只能走日子，马从位置（x,y）处出发，把棋盘的每一点都走一次，且只走一次，找出所有的路径。  
 \* @author Solin  
 \*  
 \*/  
public class chess \{  
//坐标固定的马有八种走的方式  
//用数组进行存储，方便在for中使用  
private static int fx\[\]= new int\[\]\{1,2,2,1,-1,-2,-2,-1\};  
private static int fy\[\]= new int\[\]\{2,1,-1,-2,-2,-1,1,2\};  
  
private static int RoadCount = 0;//路径条数  
private final static int n=5,m=4;  
private static int a\[\]\[\] = new int\[n\]\[m\]; //用int二维数组来表示走的路劲  
  
  
public static void main(String\[\] args) \{  
int x=0,y=0;//选择(0,0)为初始点  
   for(int i=0; i<n; i++)  
       for(int j=0; j<m; j++)  
           a\[i\]\[j\]=0;  
   a\[x\]\[y\]=1;  
  
   FindingTheWay(x,y,2);  
  
   if(RoadCount==0)\{//一条路径都没有找到  
   System.out.println("未找到可行的路径");  
   \}else\{//找到了至少一条路径  
   System.out.println("找到了"+RoadCount+"条可行的路径");  
   \}  
\}  
  
/\*\*  
\* 寻找路径的递归  
\* @param x  
\* @param y  
\* @param dep  
\*/  
public static void FindingTheWay(int x,int y,int dep)\{  
   int xx,yy;  
   for(int i=0; i<8; i++)  
   \{  
       xx=x+fx\[i\];  
       yy=y+fy\[i\];  
       if(mCheck(xx,yy)==1)  
       \{  
           a\[xx\]\[yy\]=dep;  
           if(dep==n\*m)\{  
            output();    //如果深度为n\*m，那么表示遍历结束，就打印  
           \}else\{  
            FindingTheWay(xx,yy,dep+1);  
           \}  
           a\[xx\]\[yy\]=0;     //回溯，恢复未走坐标。（如果走错，要将走错的路径还原）  
       \}  
   \}  
\}  
  
/\*\*  
\* 判断坐标是否出界，是否已经走过  
\* @param x  
\* @param y  
\* @return 0表示出界了或者已经走过了，1表示没有走过  
\*/  
public static int mCheck(int x,int y)\{  
   //判断坐标是否出界，是否已经走过  
   if(x<0||y<0||x>=n||y>=m||a\[x\]\[y\]!=0)  
       return 0;  
   return 1;  
\}  
  
/\*\*  
\* 打印路径  
\*/  
public static void output()\{  
   RoadCount++;  
   for(int i=0; i<n; i++)\{  
       for(int j=0; j<m; j++)\{  
        if(a\[i\]\[j\]<10)\{  
        System.out.print(a\[i\]\[j\]+"   ");  
        \}else\{  
        System.out.print(a\[i\]\[j\]+"  ");  
        \}  
       \}  
       System.out.println();//换行  
   \}  
   System.out.println("----------------------------");  
\}  
\}