Advertisement
theSwamz

Shortest Distance from 0,0 --> n-1,n-1 in binary matrix

Apr 19th, 2021
1,191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.90 KB | None | 0 0
  1. class Solution {
  2.    
  3.     private static final int[][] directions =
  4.         new int[][]{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
  5.    
  6.     public int shortestPathBinaryMatrix(int[][] grid) {
  7.        
  8.         // Firstly, we need to check that the start and target cells are open.
  9.         if (grid[0][0] != 0 || grid[grid.length - 1][grid[0].length - 1] != 0) {
  10.             return -1;
  11.         }
  12.        
  13.         // Set up the BFS.
  14.         Queue<int[]> queue = new ArrayDeque<>();
  15.         grid[0][0] = 1;
  16.         queue.add(new int[]{0, 0});
  17.        
  18.         // Carry out the BFS
  19.         while (!queue.isEmpty()) {
  20.             int[] cell = queue.remove();
  21.             int row = cell[0];
  22.             int col = cell[1];
  23.             int distance = grid[row][col];
  24.             if (row == grid.length - 1 && col == grid[0].length - 1) {
  25.                 return distance;
  26.             }
  27.             for (int[] neighbour : getNeighbours(row, col, grid)) {
  28.                 int neighbourRow = neighbour[0];
  29.                 int neighbourCol = neighbour[1];
  30.                 queue.add(new int[]{neighbourRow, neighbourCol});
  31.                 grid[neighbourRow][neighbourCol] = distance + 1;
  32.             }
  33.         }
  34.        
  35.         // The target was unreachable.
  36.         return -1;
  37.     }
  38.    
  39.     private List<int[]> getNeighbours(int row, int col, int[][] grid) {
  40.         List<int[]> neighbours = new ArrayList<>();
  41.         for (int i = 0; i < directions.length; i++) {
  42.             int newRow = row + directions[i][0];
  43.             int newCol = col + directions[i][1];
  44.             if (newRow < 0 || newCol < 0 || newRow >= grid.length
  45.                     || newCol >= grid[0].length
  46.                     || grid[newRow][newCol] != 0) {
  47.                 continue;    
  48.             }
  49.             neighbours.add(new int[]{newRow, newCol});
  50.         }
  51.         return neighbours;
  52.     }
  53.    
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement