Minimum Knight Moves
给一个无限大的棋盘(2d数组), 在0,0有一个马, 马走日, 求到x,y的步数
这个就是搜索问题. 因为无限大, 所以只能是bfs, 稍微剪枝一下就可以, 不过我的答案虽然过了, 但是好慢啊.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
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 } } |