Minimum Knight Moves
给一个无限大的棋盘(2d数组), 在0,0有一个马, 马走日, 求到x,y的步数
这个就是搜索问题. 因为无限大, 所以只能是bfs, 稍微剪枝一下就可以, 不过我的答案虽然过了, 但是好慢啊.
class Solution {
public int minKnightMoves(int x, int y) {
Set<String> set = new HashSet<>();
x = Math.abs(x);
y = Math.abs(y);
int[][] dirs = new int[][]{
{1,2},
{2,1},
{-1,2},
{1,-2},
{-2,1},
{2,-1},
{-2,-1},
{-1,-2}
};
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0, 0});
set.add("0|0");
int res = 0;
while(!q.isEmpty()){
int size = q.size();
for(int i = 0; i < size; i++) {
int[] cur = q.poll();
if(cur[0] == x && cur[1] ==y)
return res;
for(int[] d : dirs){
int newX = d[0] + cur[0];
int newY = d[1] + cur[1];
if(set.contains(newX+"|"+newY)){
continue;
}
else if(newX < 0 && newY < 0){
set.add(newX+"|"+newY);
continue;
}
else{
q.add(new int[]{newX, newY});
set.add(newX+"|"+newY);
}
}
}
res++;
}
return 0;//never reach
}
}