← 返回 amazon 的题目列表BFS on grid/graph (LC-style)
类型：online_judge
Given a 2D grid grid of 0/1 where 1 is walkable and 0 is blocked. Starting from (0,0), you can move 4-directionally (up/down/left/right) by 1 cell each step. Return the minimum number of steps to reach (m-1,n-1), or -1 if unreachable.
Input
First line: two integers m n
Next m lines: strings of length n consisting of 0 or 1
Output
One integer: minimum steps, or -1
Constraints
1 <= m,n <= 200
Example Input:
3 3
111
010
111
Output:
4
Example
Input
3 3
111
010
111
Output
4