贪婪算法 ---马踏棋盘

Love The Way You Lie 2022-08-10 11:55 165阅读 0赞

package com.dataconstructor.greedy;
    /*马踏棋盘问题，用贪婪算法 */ 
    public class HorseStep {
       //定义参数,x方向 y方向的增量要一致
            private static final int [] dx={-1,-2,-2,-1,1,2,2,1};// x方向的增量
            private static final int [] dy={2,1,-1,-2,-2,-1,1,2};// y方向的增量
            private static final int N=8;
            private static int [][] board=new int[N][N];//棋盘
            //计算结点出口
            public int waysOut(int x,int y){
                    int tx,ty;
                    int count=0;
                    // 结点位置非法或已踏过，返回-1 
                    if(x<0||y<0||x>=N||y>=N||board[x][y]>0){
                            return -1;
                    }
                for (int i = 0; i<N; i++) {
                    tx=x+dx[i];
                    ty=y+dy[i];
                    if(tx<0||ty<0||tx>=N||ty>=N){
                            continue;
                    }
                    if(board[tx][ty] == 0){
                            count++;
                    }
              }
              return count;
            }
        // 按结点出口数，从小到大排序 
            public void sortNode(HorseNode [] hn,int n){// 采用简单排序法，因为子结点数最多只有8 
                    int i,j,t;
                    HorseNode temp;
                    for (i = 0; i < n; ++i) {
                            for(t=i,j=i+1;j<n;++j){
                                    if(hn[j].waysOutNum<hn[t].waysOutNum){
                                            t=j;
                                    }
                                    if(t>i){
                                            temp=hn[i];
                                            hn[i]=hn[t];
                                            hn[t]=temp;
                                    }
                            }
                    }
            }
            // 搜索函数,count代表当前第几步
            public void search(int x,int y,int count){
                    int i,tx,ty;
                    HorseNode [] tExit=new HorseNode[N]; //记录出口结点的出口数
            if(count>N*N){
                 output();
                 return ;
            }
            for(i=0;i<N;i++){
             tx=x+dx[i];
             ty=y+dy[i];
             HorseNode h=new HorseNode();
             tExit[i]=h;
             tExit[i].x=tx;
             tExit[i].y=ty;
             tExit[i].waysOutNum=waysOut(tx, ty);
            }
            sortNode(tExit, N);
            for(i=0;tExit[i].waysOutNum<0;++i);
            for(;i<N;++i){
             tx=tExit[i].x;
             ty=tExit[i].y;
             board[tx][ty]=count;
             search(tx, ty, count+1);
             board[tx][ty]=0;
            }
            }
            public void output(){
                      for(int i = N - 1; i >= 0; --i){ 
                        for(int j = 0; j < N; ++j){ 
                            System.out.printf("%2d ", board[i][j]); 
                        } 
                        System.out.println(); 
                    } 
                    System.exit(0); 
            }
        //测试
            public static void main(String[] args) {
                        int x = 0; 
                    int y = 0; 
                    HorseStep test = new HorseStep(); 
                    board[x][y] = 1; 
                    test.search(x, y, 2); 
            }
    }
    /*马的节点类*/
    class HorseNode{
            int x;
            int y;
            int waysOutNum;
    }