重慶分公司
重慶分公司
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ù)本來就位1，因為出生地算一個
public static int goalNum = 8;//尋找的目標數(shù),如果goalNum為4，則目標數(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("總耗時為%d秒", (end - start) / 1000));
return;
}
}
}
}
}
public static boolean judgePosition(int[] position, int[][] map) {//判斷路況是否合法即每走完一步，落腳點必須在棋盤內(nèi)，期盼的邊界為 [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) {//如果當前數(shù)量已經(jīng)達到了遞歸的目標數(shù)，則返回true
printMap(position, map);
return true;
} else {currentNum++;//當前數(shù)量+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)) {//如果修改的坐標不合法或者說原有地圖此位置已經(jīng)為1
currentNum--;//當前數(shù)量-1
restorePosition(direction, position);//將坐標進行還原
return false;
}
map[position[0]][position[1]] = 1;
貪心算法,執(zhí)行速度為0秒//
int[] sortedDirections = getSortedDirections(position);//經(jīng)過排序的方向數(shù)組
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--;//當前數(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};//八個方向
for (int i = 0; i< directions.length; i++) {int min = i;//假設(shè)當前這個方向是離邊界最短距離
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海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
