Go语言视频零基础入门到精通

javalearner

(1) 问题描述
马的遍历问题。
      在n*m的棋盘中，马只能走"日"字。马从位置(x,y)出发，把棋盘的每一格都走一次且只走一次。找出所有路径。  (2) 问题分析     马是在棋盘的点上行走的，所以这里的棋盘是指行有N条边、列有M条边。而一个马在不出边界的情况下有8个方向
可以行走(走"日"字)，如当前坐标为(x,y)，则行走后的坐标可以为:
(x+1, y+2)
(x+1, y-2)
(x+2, y+1)
(x+2, y-1)
(x-1, y-2)
(x-1, y+2)
(x-2, y-1)
(x-2, y+1)  
  
   
   
     
   

     
   
  
      搜索的解空间是整个棋盘上的n*m个点。
    约束条件是不出边界且每个点只经过一次。
    搜索过程是从任一点(x,y)出发，按照深度优先的原则，从8个方向中尝试一个可以走的点，直到走过棋盘上所有
n*m个点。

(3)程序

1. /**  
   
2. * create on 2010.05.21 TODO 回溯算法  
   
3. *   
   
4. * @author 毛正吉  
   
5. * @version v1.0  
   
6. *   
   
7. */  
   
8. public class RecollectionSearch {   
   
9.   
   
10.     /**  
    
11.      * @param args  
    
12.      */  
    
13.     public static void main(String[] args) {   
    
14.         // 注意(0<=x< n && 0<=y< m)   
    
15.         int n = 5;   
    
16.         int m = 4;   
    
17.         int x = 0;   
    
18.         int y = 0;   
    
19.         RecollectionSearch rs = new RecollectionSearch(n, m, x, y);   
    
20.         rs.find(x, y, 2);   
    
21.         System.out.println("######################");   
    
22.         System.out.println("总解数count=" + rs.getCount());   
    
23.         System.out.println("######################");   
    
24.   
    
25.     }   
    
26.   
    
27.     // 棋盘行数   
    
28.     private int n;   
    
29.     // 棋盘列数   
    
30.     private int m;   
    
31.     // 马的起始x坐标   
    
32.     private int x;   
    
33.     // 马的起始y坐标   
    
34.     private int y;   
    
35.     // 棋盘坐标   
    
36.     private int[][] a;   
    
37.     // 求解总数   
    
38.     private int count;   
    
39.     // "日"子x坐标   
    
40.     public int[] fx = { 1, 2, 2, 1, -1, -2, -2, -1 };   
    
41.     // "日"子y坐标   
    
42.     public int[] fy = { 2, 1, -1, -2, -2, -1, 1, 2 };   
    
43.   
    
44.     /**  
    
45.      * 构造方法  
    
46.      *   
    
47.      * @param _n  
    
48.      * @param _m  
    
49.      * @param _x  
    
50.      * @param _y  
    
51.      */  
    
52.     public RecollectionSearch(int _n, int _m, int _x, int _y) {   
    
53.         n = _n;   
    
54.         m = _m;   
    
55.         x = _x;   
    
56.         y = _y;   
    
57.         a = new int[n][m];   
    
58.         for (int i = 0; i < n; i++) {   
    
59.             for (int j = 0; j < m; j++) {   
    
60.                 a[i][j] = 0;   
    
61.             }   
    
62.         }   
    
63.         // 马的起点 a[x][y]=k表示马的第k步
    
64.         a[x][y] = 1;   
    
65.         count = 0;   
    
66.     }   
    
67.   
    
68.     public void find(int x, int y, int dep) {   
    
69.         int i, xx, yy;   
    
70.         for (i = 0; i < 8; i++) {   
    
71.             xx = x + fx[i];   
    
72.             yy = y + fy[i];   
    
73.             // 判断新坐标是否出界，是否已走过   
    
74.             if (check(xx, yy) == 1) {   
    
75.                 a[xx][yy] = dep;   
    
76.                 if (dep == n * m) {   
    
77.                     output();   
    
78.                 } else {   
    
79.                     // 从新坐标出发，递归下一层   
    
80.                     find(xx, yy, dep + 1);   
    
81.                 }   
    
82.                 // 回溯，恢复未走标志   
    
83.                 a[xx][yy] = 0;   
    
84.             }   
    
85.         }   
    
86.     }   
    
87.   
    
88.     /**  
    
89.      * 判断新坐标是否出界，是否已走过  
    
90.      *   
    
91.      * @param xx  
    
92.      * @param yy  
    
93.      * @return  
    
94.      */  
    
95.     public int check(int xx, int yy) {   
    
96.         if (xx >= n || yy >= m || xx < 0 || yy < 0 || a[xx][yy] != 0) {   
    
97.             return 0;   
    
98.         }   
    
99.         return 1;   
    
100.     }   
     
101.   
     
102.     /**  
     
103.      * 输出结果  
     
104.      */  
     
105.     public void output() {   
     
106.         count++;   
     
107.         System.out.println("count=" + count);   
     
108.         for (int y = 0; y < n; y++) {   
     
109.             System.out.println("");   
     
110.             for (int x = 0; x < m; x++) {   
     
111.                 System.out.printf("%4d",a[y][x]);   
     
112.             }   
     
113.         }   
     
114.         System.out.println("");   
     
115.     }   
     
116.   
     
117.     public int getN() {   
     
118.         return n;   
     
119.     }   
     
120.   
     
121.     public void setN(int n) {   
     
122.         this.n = n;   
     
123.     }   
     
124.   
     
125.     public int getM() {   
     
126.         return m;   
     
127.     }   
     
128.   
     
129.     public void setM(int m) {   
     
130.         this.m = m;   
     
131.     }   
     
132.   
     
133.     public int getCount() {   
     
134.         return count;   
     
135.     }   
     
136.   
     
137.     public void setCount(int count) {   
     
138.         this.count = count;   
     
139.     }   
     
140.   
     
141.     public int getX() {   
     
142.         return x;   
     
143.     }   
     
144.   
     
145.     public void setX(int x) {   
     
146.         this.x = x;   
     
147.     }   
     
148.   
     
149.     public int getY() {   
     
150.         return y;   
     
151.     }   
     
152.   
     
153.     public void setY(int y) {   
     
154.         this.y = y;   
     
155.     }   
     
156. }  
     

复制代码

运行：

count=3
.........................................略..................................................................
count=32   1   6   17   12
18 13  8    5
7   2   11   16
14 19 4     9
3   10 15   20
######################
总解数count=32
######################


  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/26/000605015.zip