Shortest Path in Binary Matrix

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 lengthkif and only if it is composed of cellsC_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.

public class Solution {
    public int ShortestPathBinaryMatrix(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;

        if(grid[0][0] == 1 || grid[m-1][n-1] == 1){
            return -1;
        }
        bool[][] isVisited = new bool[m][];
        for(int i = 0; i < m ; i++){
            isVisited[i] = new bool[n];
        }

        Queue<int[]> q = new Queue<int[]>();

        q.Enqueue(new int[]{0, 0});
        isVisited[0][0] = true;

        int[][] dirs = new int[8][];

        dirs[0] = new int[]{-1, 0};
        dirs[1] = new int[]{1, 0};
        dirs[2] = new int[]{0, -1};
        dirs[3] = new int[]{0, 1};
        dirs[4] = new int[]{-1,-1};
        dirs[5] = new int[]{1,-1};
        dirs[6] = new int[]{-1, 1};
        dirs[7] = new int[]{1,1};

        int ans = 0;

        while(q.Count > 0){
            int size = q.Count;

            for(int l=0 ;l <size;l++) {

                var curr = q.Dequeue();

                if(curr[0] == m - 1 && curr[1] == n -1){
                    return ans + 1;
                }
                for(int i = 0; i < 8; i++){
                    int x = curr[0] + dirs[i][0];
                    int y = curr[1] + dirs[i][1];

                    if(x < 0 || x >= m || y < 0 || y >= m || isVisited[x][y] || grid[x][y] == 1){
                        continue;
                    }
                    q.Enqueue(new int[]{x, y});
                    isVisited[x][y] = true;
                }
            }
            ans ++; 
        }
        return -1;
    }
}

Last updated

Was this helpful?