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

nkweew

(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)程序

/**  
* create on 2010.05.21 TODO 回溯算法  
*   
* @author 毛正吉  
* @version v1.0  
*   
*/  
public class RecollectionSearch {   
  
    /**  
     * @param args  
     */  
    public static void main(String[] args) {   
        // 注意(0<=x< n && 0<=y< m)   
        int n = 5;   
        int m = 4;   
        int x = 0;   
        int y = 0;   
        RecollectionSearch rs = new RecollectionSearch(n, m, x, y);   
        rs.find(x, y, 2);   
        System.out.println("######################");   
        System.out.println("总解数count=" + rs.getCount());   
        System.out.println("######################");   
  
    }   
  
    // 棋盘行数   
    private int n;   
    // 棋盘列数   
    private int m;   
    // 马的起始x坐标   
    private int x;   
    // 马的起始y坐标   
    private int y;   
    // 棋盘坐标   
    private int[][] a;   
    // 求解总数   
    private int count;   
    // "日"子x坐标   
    public int[] fx = { 1, 2, 2, 1, -1, -2, -2, -1 };   
    // "日"子y坐标   
    public int[] fy = { 2, 1, -1, -2, -2, -1, 1, 2 };   
  
    /**  
     * 构造方法  
     *   
     * @param _n  
     * @param _m  
     * @param _x  
     * @param _y  
     */  
    public RecollectionSearch(int _n, int _m, int _x, int _y) {   
        n = _n;   
        m = _m;   
        x = _x;   
        y = _y;   
        a = new int[n][m];   
        for (int i = 0; i < n; i++) {   
            for (int j = 0; j < m; j++) {   
                a[j] = 0;   
            }   
        }   
        // 马的起点 a[x][y]=k表示马的第k步
        a[x][y] = 1;   
        count = 0;   
    }   
  
    public void find(int x, int y, int dep) {   
        int i, xx, yy;   
        for (i = 0; i < 8; i++) {   
            xx = x + fx;   
            yy = y + fy;   
            // 判断新坐标是否出界，是否已走过   
            if (check(xx, yy) == 1) {   
                a[xx][yy] = dep;   
                if (dep == n * m) {   
                    output();   
                } else {   
                    // 从新坐标出发，递归下一层   
                    find(xx, yy, dep + 1);   
                }   
                // 回溯，恢复未走标志   
                a[xx][yy] = 0;   
            }   
        }   
    }   
  
    /**  
     * 判断新坐标是否出界，是否已走过  
     *   
     * @param xx  
     * @param yy  
     * @return  
     */  
    public int check(int xx, int yy) {   
        if (xx >= n || yy >= m || xx < 0 || yy < 0 || a[xx][yy] != 0) {   
            return 0;   
        }   
        return 1;   
    }   
  
    /**  
     * 输出结果  
     */  
    public void output() {   
        count++;   
        System.out.println("count=" + count);   
        for (int y = 0; y < n; y++) {   
            System.out.println("");   
            for (int x = 0; x < m; x++) {   
                System.out.printf("%4d",a[y][x]);   
            }   
        }   
        System.out.println("");   
    }   
  
    public int getN() {   
        return n;   
    }   
  
    public void setN(int n) {   
        this.n = n;   
    }   
  
    public int getM() {   
        return m;   
    }   
  
    public void setM(int m) {   
        this.m = m;   
    }   
  
    public int getCount() {   
        return count;   
    }   
  
    public void setCount(int count) {   
        this.count = count;   
    }   
  
    public int getX() {   
        return x;   
    }   
  
    public void setX(int x) {   
        this.x = x;   
    }   
  
    public int getY() {   
        return y;   
    }   
  
    public void setY(int y) {   
        this.y = y;   
    }   
}  

运行：


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
######################