馬踏棋盤算法（java+貪心算法）-創(chuàng)新互聯

import java.util.Arrays;

public class Test {public static final int LEFT_UP = 0;//左上
    public static final int UP_LEFT = 1;//上左
    public static final int UP_RIGHT = 2;//上右
    public static final int RIGHT_UP = 3;//右上
    public static final int RIGHT_DOWN = 4;//右下
    public static final int DOWN_RIGHT = 5;//下右
    public static final int DOWN_LEFT = 6;//下左
    public static final int LEFT_DOWN = 7;//左下
    public static int currentNum = 1;//馬的步數本來就位1，因為出生地算一個
    public static int goalNum = 8;//尋找的目標數,如果goalNum為4，則目標數為16

    public static void main(String[] args) {long start = System.currentTimeMillis();
        for (int x = 0; x< goalNum; x++) {for (int y = 0; y< goalNum; y++) {int[] position = {x, y};//馬兒的初始位置
                int[][] map = new int[goalNum][goalNum];//地圖
                map[position[0]][position[1]] = 1;
                for (int direction = LEFT_UP; direction<= LEFT_DOWN; direction++) {if (move(direction, position, map)) {//如果遞歸成功
                        long end = System.currentTimeMillis();
                        System.out.println(String.format("總耗時為%d秒", (end - start) / 1000));
                        return;
                    }
                }
            }
        }
    }

    public static boolean judgePosition(int[] position, int[][] map) {//判斷路況是否合法即每走完一步，落腳點必須在棋盤內，期盼的邊界為   [0,0]-[3,3]，且棋盤當前位置不能重新踩
        return ((position[0] >= 0 && position[0]<= goalNum - 1) && (position[1] >= 0 && position[1]<= goalNum - 1)) && map[position[0]][position[1]] != 1;
    }

    //遞歸一次，currentNum就得+1
    public static boolean move(int direction, int[] position, int[][] map) {//移動
        if (currentNum == goalNum * goalNum) {//如果當前數量已經達到了遞歸的目標數，則返回true
            printMap(position, map);
            return true;
        } else {currentNum++;//當前數量+1
            int[] positionCopy = Arrays.copyOf(position, position.length);//一進入這個方法，就將position的值保存下來
            int[][] mapCopy = new int[goalNum][goalNum];
            for (int i = 0; i< goalNum; i++) {for (int j = 0; j< goalNum; j++) {mapCopy[i][j] = map[i][j];
                }
            }
            modifyPosition(direction, position);//修改位置
            if (!judgePosition(position, map)) {//如果修改的坐標不合法或者說原有地圖此位置已經為1
                currentNum--;//當前數量-1
                restorePosition(direction, position);//將坐標進行還原
                return false;
            }
            map[position[0]][position[1]] = 1;

            貪心算法,執(zhí)行速度為0秒//
            int[] sortedDirections = getSortedDirections(position);//經過排序的方向數組
            for (int nextDirection : sortedDirections) {if (move(nextDirection, position, map)) {//如果遞歸成功
                    printMap(positionCopy, mapCopy);
                    return true;
                }
            }
            

            //無貪心算法/
//            for (int nextDirection = LEFT_UP; nextDirection<= LEFT_DOWN; nextDirection++) {//沒貪心算法
//                if (move(nextDirection, position, map)) {//如果遞歸成功
//                    printMap(positionCopy, mapCopy);
//                    return true;
//                }
//            }
            

            map[position[0]][position[1]] = 0;
            restorePosition(direction, position);//將坐標進行還原
            currentNum--;//當前數量-1
            return false;
        }
    }

    public static int[] getSortedDirections(int[] position) {//將原先代碼執(zhí)行速度從10分鐘提升到0秒的關鍵所在
        int[] directions = {LEFT_UP, UP_LEFT, UP_RIGHT, RIGHT_UP, RIGHT_DOWN, DOWN_RIGHT, DOWN_LEFT, LEFT_DOWN};//八個方向
        for (int i = 0; i< directions.length; i++) {int min = i;//假設當前這個方向是離邊界最短距離
            for (int j = i; j< directions.length; j++) {int[] position1 = {position[0], position[1]};
                int positionDistance = 0;
                modifyPosition(directions[j], position1);
                if (position1[0] >3) {positionDistance += goalNum - 1 - position1[0];
                } else {positionDistance += position1[0];
                }
                if (position1[1] >3) {positionDistance += goalNum - 1 - position1[1];
                } else {positionDistance += position1[1];
                }

                int[] position2 = {position[0], position[1]};
                int minPositionDistance = 0;
                modifyPosition(directions[min], position2);
                if (position2[0] >3) {minPositionDistance += goalNum - 1 - position2[0];
                } else {minPositionDistance += position2[0];
                }
                if (position2[1] >3) {minPositionDistance += goalNum - 1 - position2[1];
                } else {minPositionDistance += position2[1];
                }
                if (positionDistance< minPositionDistance) {min = j;
                }
            }
            int temp = directions[i];
            directions[i] = directions[min];
            directions[min] = temp;
        }
        return directions;
    }

    public static void modifyPosition(int direction, int[] position) {//修改位置
        switch (direction) {case LEFT_UP:
                position[0] -= 1;
                position[1] -= 2;
                break;
            case UP_LEFT:
                position[0] -= 2;
                position[1] -= 1;
                break;
            case UP_RIGHT:
                position[0] -= 2;
                position[1] += 1;
                break;
            case RIGHT_UP:
                position[0] -= 1;
                position[1] += 2;
                break;
            case RIGHT_DOWN:
                position[0] += 1;
                position[1] += 2;
                break;
            case DOWN_RIGHT:
                position[0] += 2;
                position[1] += 1;
                break;
            case DOWN_LEFT:
                position[0] += 2;
                position[1] -= 1;
                break;
            case LEFT_DOWN:
                position[0] += 1;
                position[1] -= 2;
                break;
        }
    }

    public static void restorePosition(int direction, int[] position) {//還原位置
        switch (direction) {case LEFT_UP:
                position[0] += 1;
                position[1] += 2;
                break;
            case UP_LEFT:
                position[0] += 2;
                position[1] += 1;
                break;
            case UP_RIGHT:
                position[0] += 2;
                position[1] -= 1;
                break;
            case RIGHT_UP:
                position[0] += 1;
                position[1] -= 2;
                break;
            case RIGHT_DOWN:
                position[0] -= 1;
                position[1] -= 2;
                break;
            case DOWN_RIGHT:
                position[0] -= 2;
                position[1] -= 1;
                break;
            case DOWN_LEFT:
                position[0] -= 2;
                position[1] += 1;
                break;
            case LEFT_DOWN:
                position[0] -= 1;
                position[1] += 2;
                break;
        }
    }

    public static void printMap(int[] position, int[][] map) {for (int i = 0; i< goalNum; i++) {for (int j = 0; j< goalNum; j++) {System.out.print(map[i][j] + "  ");
            }
            System.out.println();
        }
        System.out.println(Arrays.toString(position));
        System.out.println("=======================");
    }
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

創(chuàng)新互聯公司是一家集網站建設,古冶企業(yè)網站建設,古冶品牌網站建設,網站定制,古冶網站建設報價,網絡營銷,網絡優(yōu)化,古冶網站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統企業(yè)提升企業(yè)形象加強企業(yè)競爭力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯網需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網站。

分享題目：馬踏棋盤算法（java+貪心算法）-創(chuàng)新互聯
標題網址：http://muchs.cn/article20/dcppco.html

成都網站建設公司_創(chuàng)新互聯，為您提供動態(tài)網站、網站收錄、搜索引擎優(yōu)化、域名注冊、自適應網站、靜態(tài)網站

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯