Shortest Path to Get Food
给一个2d数组, 找两个格子之间的步数.
|
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 |
class Solution { public int getFood(char[][] grid) { for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { if(grid[i][j] == '*') return bfs(grid, i, j); } } return -1;//never reach } public int bfs(char[][] grid, int i, int j){ Queue<int[]> q = new LinkedList<>(); q.add(new int[]{i,j, 0}); int[][] dirs = new int[][]{ {0,1}, {1,0}, {-1,0}, {0,-1} }; while(!q.isEmpty()){ int[] cur = q.poll(); for(int[] d : dirs) { int newX = cur[0] + d[0]; int newY = cur[1] + d[1]; if(newX < 0 || newX >= grid.length || newY < 0 || newY >= grid[0].length) continue; else if(grid[newX][newY] == '#') return cur[2] + 1; else if(grid[newX][newY] == 'O'){ grid[newX][newY] = 'X'; q.add(new int[]{newX, newY, cur[2] + 1}); } } } return -1; } } |