← 返回比赛
已结束 GESP挑战赛#33
← 上一题 下一题 →

A7449 | 迷宫寻路

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

$Sherry$ 在上学路上误入空洞迷宫，这个迷宫是一个 $n$ 行 $m$ 列的数字矩阵，第 $i$ 行第 $j$ 列上有一个数字 $a_{i,j}$。

- 如果 $a_{i,j}=0$，则该位置为空地，可以移动到该位置。
- 如果 $a_{i,j}=1$，则该位置为障碍物，不能移动到该位置。
- 只能移动到当前位置的上下左右四个方向之一，且只能移动到相邻的格子。

$Sherry$ 会出现在迷宫的某个空地位置。$Sherry$ 每次可以选择向上、下、左、右中的一个方向移动一格，不能移动到障碍物上。

她希望尽快离开迷宫。当她移动到行号小于 $1$ 或大于 $n$，或列号小于 $1$ 或大于 $m$ 的位置时，她就成功离开迷宫。

现在，你要帮 $Sherry$ 算一算，对于每次询问的初始位置，她在至少多少次移动后会离开迷宫，或报告她永远不会离开迷宫。

输入格式

第一行输入三个整数 $n,m,k$，分别表示迷宫的行数 $n$、列数 $m$ 和询问次数 $k$。

接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $a$。

接下来 $k$ 行，每行两个整数 $x_{i},y_{i}$，表示第 $i$ 次查询的初始位置在 $x_{i}$ 行 $y_{i}$ 列。

保证每次询问的初始位置均为空地。

输出格式

输出 $k$ 行，每行一个整数，表示一次查询的答案。如果本次查询中她永远无法离开迷宫，输出 $-1$。

输入输出样例

输入 #1
5 5 4
1 0 1 1 1
1 0 0 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
2 2
2 3
4 4
1 2
输出 #1
2
3
-1
1
C++ 编辑器
输入
输出