求解，两马走日问题...拼多多补招一面代码题

感觉思路还是比较简单的，我们可以将马分为A,B，要跳的位置分为a,b 行走策略 可以用反证法证明一匹马先走，另一匹马后走，与不规定马走的顺序的最优解相等。 因此，根据马和地方的不同，我们将问题分为四个小问题，即： A马先走到a点，然后B马走到b点 A马先走到b点，然后B马走到a点 B马先走到a点，然后A马走到b点 B马先走到b点，然后A马走到a点 分别求以上四个小问题的最优解，然后再从四个小问题的解中选取最优解即可。 算法 这里算法是要设计给定一个图，一匹马，一个目的地，求马到达该点的最短跳数。 方法就是和上面几个人的说法一致，用BFS即可，另用一张表记录马跳到当前该点最短跳数。

求不沉。。。

应该是斐波那 数列解题思路吧

状态是两个马的当前位置，这样就是四个整数值，进行dfs结合备忘录即可

记忆化搜索

IDA*   估价函数h为两马为国际象棋的马时需要的步数。

是两匹马走到同一个位置么？

马会不会被马挡到马脚什么的啊？不会的话，把马bfs一遍，然后枚举每个h位置相加情况就好了

import java.util.*; class Position2D { int x; int y; Position2D(int x, int y){ this.x = x; this.y = y; } public boolean equals(Object obj){ return obj instanceof Position2D && (((Position2D)obj).x == this.x) &&(((Position2D)obj).y == this.y); } } class Config { Position2D horseA; Position2D horseB; char[][] record; int[][] isVisited; int stepUsed; Config(Position2D horseA, Position2D horseB, char[][] record, int[][] isVisited, int stepUsed){ this.horseA = horseA; this.horseB = horseB; this.record = record; this.isVisited = isVisited; this.stepUsed = stepUsed; } } class Main12{ public static void main(String[] args){ char[][] record = { {'H','*','*','h','*'}, {'*','*','h','*','*'}, {'*','*','H','#','#'}, {'#','#','*','*','*'}, {'*','*','*','*','*'} }; int[][] isVisited = new int[record.length][record[0].length]; isVisited[0][0] = 1; isVisited[2][2] = 2; System.out.println(minimumJumps(new Position2D(0,0),new Position2D(2,2), new Position2D(3,0),new Position2D(2,1),record,isVisited,0)); } static boolean isValid(char[][] record, Position2D ori, Position2D dest, Position2D another){ //避免边界 if(dest.x<0||dest.x>=record[0].length||dest.y<0||dest.y>=record.length) return false; //避免两马重合 if(dest.equals(another)) return false; //避免障碍物 if(record[dest.y][dest.x] == '#') return false; //示意图： 蹩马腿情况示意图 共8种情况， 可以是另一只马（'H'）或者障碍物('#') // 0 1 2 3 4 5 6 7 8 横坐标 // 1 1 3 // 2 2 4 // 3 m // 4 5 8 // 5 6 7 //m可以抵达的位置 //纵坐标 //case 2 if(dest.y == ori.y - 1 && dest.x == ori.x - 2 && (record[ori.y-1][ori.x-1]=='#'||record[ori.y][ori.x-1]=='#'|| record[ori.y-1][ori.x-1]=='H'||record[ori.y][ori.x-1]=='H')) return false; //case 1 if(dest.y == ori.y - 2 && dest.x == ori.x - 1 && (record[ori.y-1][ori.x]=='#'||record[ori.y-1][ori.x-1]=='#'|| record[ori.y-1][ori.x]=='H'||record[ori.y-1][ori.x-1]=='H')) return false; //case 5 if(dest.y == ori.y + 1 && dest.x == ori.x - 2 && (record[ori.y+1][ori.x-1]=='#'||record[ori.y][ori.x-1]=='#'||record[ori.y+1][ori.x-1]=='H'||record[ori.y][ori.x-1]=='H')) return false; //case 6 if(dest.y == ori.y + 2 && dest.x == ori.x - 1 && (record[ori.y+1][ori.x]=='#'||record[ori.y+1][ori.x-1]=='#'||record[ori.y+1][ori.x]=='H'||record[ori.y+1][ori.x-1]=='H')) return false; //case 3 if(dest.y == ori.y - 2 && dest.x == ori.x + 1 && (record[ori.y-1][ori.x]=='#'||record[ori.y-1][ori.x+1]=='#'||record[ori.y-1][ori.x]=='H'||record[ori.y-1][ori.x+1]=='H')) return false; //case 4 if(dest.y == ori.y - 1 && dest.x == ori.x + 2 && (record[ori.y-1][ori.x+1]=='#'||record[ori.y][ori.x+1]=='#'||record[ori.y-1][ori.x+1]=='H'||record[ori.y][ori.x+1]=='H')) return false; //case 8 if(dest.y == ori.y + 1 && dest.x == ori.x + 2 && (record[ori.y][ori.x+1]=='#'||record[ori.y+1][ori.x+1]=='#'||record[ori.y][ori.x+1]=='H'||record[ori.y+1][ori.x+1]=='H')) return false; //case 7 if(dest.y == ori.y + 2 && dest.x == ori.x + 1 && (record[ori.y+1][ori.x+1]=='#'||record[ori.y+1][ori.x]=='#'||record[ori.y+1][ori.x+1]=='H'||record[ori.y+1][ori.x]=='H')) return false; return true; } //可能的移动 static int[][] possibleMove = {{-1,-2},{-2,-1},{1,-2},{2,-1},{-2,1},{-1,2},{1,2},{2,1}}; //BFS Queue static Queue<Config> queue = new LinkedList<>(); static int minimumJumps(Position2D horseA, Position2D horseB, Position2D d1, Position2D d2, char[][] record, int[][] isVisited, int stepUsed){ queue.offer(new Config(horseA,horseB,record,isVisited,stepUsed)); while(!queue.isEmpty()){ Config current = queue.poll(); for(int[] pm: possibleMove){ horseA = current.horseA; horseB = current.horseB; record = current.record; isVisited = current.isVisited; stepUsed = current.stepUsed; Position2D destinationA = new Position2D(horseA.x+pm[0],horseA.y+pm[1]); if(!horseA.equals(d1) &&isValid(record,horseA,destinationA,horseB) &&isVisited[destinationA.y][destinationA.x]!=1&&isVisited[destinationA.y][destinationA.x]!=3){ char[][] newRecord =new char[record.length][record[0].length]; arrayCopy(record,newRecord); newRecord[horseA.y][horseA.x] = '*'; newRecord[destinationA.y][destinationA.x] = 'H'; int[][] newIsVisited = new int[isVisited.length][isVisited[0].length]; arrayCopy(isVisited,newIsVisited); newIsVisited[destinationA.y][destinationA.x]++; if(newRecord[d1.y][d1.x] == 'H'&&newRecord[d2.y][d2.x] == 'H') return stepUsed + 1; queue.offer(new Config(destinationA,horseB,newRecord,newIsVisited,stepUsed+1)); } Position2D destinationB = new Position2D(horseB.x+pm[0],horseB.y+pm[1]); if(!horseB.equals(d2) &&isValid(record,horseB,destinationB,horseA)&& isVisited[destinationB.y][destinationB.x]!=2 && isVisited[destinationB.y][destinationB.x]!=3){ char[][] newRecord =new char[record.length][record[0].length]; arrayCopy(record,newRecord); newRecord[horseB.y][horseB.x] = '*'; newRecord[destinationB.y][destinationB.x] = 'H'; int[][] newIsVisited = new int[isVisited.length][isVisited[0].length]; arrayCopy(isVisited,newIsVisited); newIsVisited[destinationB.y][destinationB.x]+=2; if(newRecord[d1.y][d1.x] == 'H'&&newRecord[d2.y][d2.x] == 'H') return stepUsed + 1; queue.offer(new Config(horseA,destinationB,newRecord,newIsVisited,stepUsed+1)); } } } return stepUsed+1; } public static void arrayCopy(int[][] aSource, int[][] aDestination) { for (int i = 0; i < aSource.length; i++) { System.arraycopy(aSource[i], 0, aDestination[i], 0, aSource[i].length); } } public static void arrayCopy(char[][] aSource, char[][] aDestination) { for (int i = 0; i < aSource.length; i++) { System.arraycopy(aSource[i], 0, aDestination[i], 0, aSource[i].length); } } }

简单写了代码，求大佬们斧正