Shortest Path in Binary Matrix

medium

Acceptance: 44%

GraphsBFS

In an n-by-n binary grid (0 = passable, 1 = blocked), find the length of the shortest path from the top-left to the bottom-right cell. Movement is allowed in all eight directions (including diagonals). The path length counts the number of cells visited. Return -1 if no such path exists.

Examples

Example 1:

Input:grid = [[0,0,1],[0,0,0],[1,0,0]]

Output:3

Explanation: Path (0,0) -> (1,1) -> (2,2) visits 3 cells.

Example 2:

Input:grid = [[0,1],[1,0]]

Output:-1

Explanation: No clear path exists because the cells adjacent to start and end are blocked.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Shortest Path in Binary Matrix

Examples

Hints

Related Problems