Guest User

Untitled

a guest
Aug 18th, 2019
68
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public static int minDist(int rows, int cols, int[][] grid){
  2. int n = grid.length;
  3. if(n == 1){
  4. return grid[0][0] == 1? 1: -1;
  5. }
  6. int[] dx = new int[]{0, -1, 0, 1};
  7. int[] dy = new int[]{1, 0, -1, 0};
  8. boolean[][] visited = new boolean[rows][cols];
  9. Queue<int[]> q = new LinkedList<>();
  10. q.offer(new int[]{0, 0});
  11. visited[0][0] = true;
  12. int res = 0;
  13. while(!q.isEmpty()){
  14. int size = q.size();
  15. for (int i = 0; i < size; i++){
  16. int[] arr = q.poll();
  17. if(arr[0] == rows && arr[1] == cols){
  18. return -1;
  19. }
  20. if(grid[arr[0]][arr[1]] == 9){
  21. return res;
  22. }
  23. for(int j = 0; j < 4; j++){
  24. int nx = arr[0] + dx[j];
  25. int ny = arr[1] + dy[j];
  26. if(nx < 0 || nx >= rows || ny < 0 || ny >= cols || visited[nx][ny]){
  27. continue;
  28. }
  29. if(grid[nx][ny] == 0) continue;
  30. q.offer(new int[]{nx, ny});
  31. visited[nx][ny] = true;
  32. }
  33. }
  34. res++;
  35. }
  36. return -1;
  37. }
RAW Paste Data