Amazon Fresh — Delivery Grid BFS

In the grid, 1 is passable, 0 is an obstacle, and 9 is the unique destination. Starting from the top-left corner and moving between 4-directionally adjacent cells, return the minimum number of steps to reach 9; output −1 if there is no path.

输入格式

The first line contains r c (1..1000), followed by r strings of length c over the characters 019; the top-left corner is passable (it may itself be 9), and there is exactly one 9.

输出格式

Output a single integer answer.

样例 1

输入：

3 3
100
100
191

输出：

3

样例 2

输入：

1 1
9

输出：

0

样例 3

输入：

2 2
10
09

输出：

-1

样例说明

Example 1: two steps down and one step right reach 9, so the answer is 3. Example 2: the start is the destination, so the answer is 0. Example 3: both exits are 0, so the answer is −1.