U96092.DFS变式题

普及/提高-

通过率：0%

时间限制：10.00s

内存限制：512MB

题目描述

你有一个n*m的迷宫,"0"表示不能走,"1"表示能走
你每秒可以向上下左右移动或保持不动
你在(1,1),出口在(n,m)
题目还会给你t个数对(A,B)表示在第Ti秒时,以(Ai,Bi)为中心的九宫格是不能走的,就是第Ti秒时,你不能在以(Ai,Bi)为中心的九宫格里
(Ai,Bi)=（-1，-1）时表示没有
你需要求出走出迷宫的最小时间，如走不出，输出"-1"

输入格式

第一行三个数,n,m,t
接下来是n*m的二维数组
最后是t行，每行两个数，Ai,Bi

输出格式

一行答案

输入输出样例

输入#1

7 7 7
1 0 0 1 0 0 1
1 1 1 1 1 1 1
0 0 1 0 0 0 1
0 1 1 1 1 0 0
0 0 0 1 1 1 0
0 0 0 0 0 1 0
1 1 1 1 1 1 1
-1 -1
-1 -1
-1 -1
4 3
4 3
1 7
-1 -1

输出#1

输入#2

7 7 7
1 0 0 1 0 0 1
1 1 1 1 1 1 1
0 0 0 0 0 0 1
0 1 1 1 1 0 0
0 0 0 1 1 1 0
0 0 0 0 0 1 0
1 1 1 1 1 1 1
-1 -1
-1 -1
-1 -1
4 3
4 3
-1 -1
-1 -1

输出#2

-1

说明/提示

以(Ai,Bi)为中心的九宫格不会有出生地和出口

样例1解释
下右右不动（要走的路没了）不动（要走的路没了）下
下右右下右下下右
0<=n,m,t<=100
本题空间限制512MB 时间限制9999ms

首页