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;//馬的步數(shù)本來(lái)就位1，因?yàn)槌錾厮阋粋€(gè)
    public static int goalNum = 8;//尋找的目標(biāo)數(shù),如果goalNum為4，則目標(biāo)數(shù)為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("總耗時(shí)為%d秒", (end - start) / 1000));
                        return;
                    }
                }
            }
        }
    }

    public static boolean judgePosition(int[] position, int[][] map) {//判斷路況是否合法即每走完一步，落腳點(diǎn)必須在棋盤(pán)內(nèi)，期盼的邊界為   [0,0]-[3,3]，且棋盤(pán)當(dāng)前位置不能重新踩
        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) {//移動(dòng)
        if (currentNum == goalNum * goalNum) {//如果當(dāng)前數(shù)量已經(jīng)達(dá)到了遞歸的目標(biāo)數(shù)，則返回true
            printMap(position, map);
            return true;
        } else {currentNum++;//當(dāng)前數(shù)量+1
            int[] positionCopy = Arrays.copyOf(position, position.length);//一進(jìn)入這個(gè)方法，就將position的值保存下來(lái)
            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)) {//如果修改的坐標(biāo)不合法或者說(shuō)原有地圖此位置已經(jīng)為1
                currentNum--;//當(dāng)前數(shù)量-1
                restorePosition(direction, position);//將坐標(biāo)進(jìn)行還原
                return false;
            }
            map[position[0]][position[1]] = 1;

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

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

            map[position[0]][position[1]] = 0;
            restorePosition(direction, position);//將坐標(biāo)進(jìn)行還原
            currentNum--;//當(dāng)前數(shù)量-1
            return false;
        }
    }

    public static int[] getSortedDirections(int[] position) {//將原先代碼執(zhí)行速度從10分鐘提升到0秒的關(guān)鍵所在
        int[] directions = {LEFT_UP, UP_LEFT, UP_RIGHT, RIGHT_UP, RIGHT_DOWN, DOWN_RIGHT, DOWN_LEFT, LEFT_DOWN};//八個(gè)方向
        for (int i = 0; i< directions.length; i++) {int min = i;//假設(shè)當(dāng)前這個(gè)方向是離邊界最短距離
            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)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),古冶企業(yè)網(wǎng)站建設(shè),古冶品牌網(wǎng)站建設(shè),網(wǎng)站定制,古冶網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷(xiāo),網(wǎng)絡(luò)優(yōu)化,古冶網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M(mǎn)足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專(zhuān)業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶(hù)成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

分享題目：馬踏棋盤(pán)算法（java+貪心算法）-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://jinyejixie.com/article20/dcppco.html

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

廣告

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