846. Shortest Path in a Binary Matrix
0
Medium
Given a binary matrix grid of size n x n, find the length of the shortest clear path from the top-left cell to the bottom-right cell. If there is no clear path, return -1.
A clear path in a binary matrix is a path that consists of cells with a value of 0. The path must be 8-directionally connected, meaning that adjacent cells must be different and share an edge or a corner. The length of a clear path is determined by the number of visited cells along the path.
Input Format
The first line of input contains an integer N, which represents the dimension of the grid. The next N lines contain binary arrays of length N, representing the binary matrix.
Output Format
The output is an integer representing the length of the shortest path.
Example
Input
3
0 0 0
1 1 0
1 1 0
Output
4
Constraints
1 <= N <= 100
Loading...
View Submissions
Console