Formatted question description: https://leetcode.ca/all/1091.html

1091. Shortest Path in Binary Matrix

Level

Medium

Description

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

  • Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
  • C_1 is at location (0, 0) (ie. has value grid[0][0])
  • C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
  • If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).

Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

Example 1:

Input: [[0,1],[1,0]]

Image text

Output: 2

Image text

Example 2:

Input: [[0,0,0],[1,1,0],[1,1,0]]

Image text

Output: 4

Image text

Note:

  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[r][c] is 0 or 1

Solution

If grid has 0 rows or 0 columns, then such a path does not exist. Also if the top-left corner of grid is blocked or the bottom-right corner of grid is blocked, then such a path does not exist. In these cases, return -1.

Use breadth first search to find the length of the shortest path. The top-left corner has path length 1. Starting from the top-left corner, search all adjacent cells that are connected 8-directionally. If an adjacent cell is empty and not visited, update the distance of the adjacent cell and add it to the queue for further search.

If the bottom-right corner can be reached, return the length of the shortest path. Otherwise, return -1.

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return -1;
        int side = grid.length;
        if (grid[0][0] == 1 || grid[side - 1][side - 1] == 1)
            return -1;
        final int BLOCK = -1;
        final int WHITE = 0;
        final int GRAY = 1;
        final int BLACK = 2;
        int[][] colors = new int[side][side];
        int[][] distances = new int[side][side];
        for (int i = 0; i < side; i++) {
            for (int j = 0; j < side; j++) {
                if (grid[i][j] == 0) {
                    colors[i][j] = WHITE;
                    distances[i][j] = Integer.MAX_VALUE;
                } else {
                    colors[i][j] = BLOCK;
                    distances[i][j] = -1;
                }
            }
        }
        colors[0][0] = GRAY;
        distances[0][0] = 1;
        int[][] directions = { {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1} };
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0], column = cell[1];
            int distance = distances[row][column];
            for (int[] direction : directions) {
                int newRow = row + direction[0], newColumn = column + direction[1];
                if (newRow >= 0 && newRow < side && newColumn >= 0 && newColumn < side && colors[newRow][newColumn] == WHITE) {
                    colors[newRow][newColumn] = GRAY;
                    distances[newRow][newColumn] = distance + 1;
                    queue.offer(new int[]{newRow, newColumn});
                }
            }
            colors[row][column] = BLACK;
        }
        return distances[side - 1][side - 1] == Integer.MAX_VALUE ? -1 : distances[side - 1][side - 1];
    }
}

All Problems

All Solutions