No submission language available for this problem.

题目描述

你是一名年轻的探险家，正在探索一座神秘的迷宫。这个迷宫由数字 $0$ 和 $1$ 组成，其中 $0$ 表示空地，$1$ 表示障碍物。你需要从起点集合中任选一个点作为出发点，从终点集合中任选一个点作为终点，到达终点。

然而，这个迷宫非常危险，到处都是陷阱和怪物。你需要谨慎地选择路径，才能顺利到达终点。每次移动只能走到四个相邻格子，每个格子的移动代价不同。你需要在这些格子中做出选择，才能找到通往终点的最短路径，算出最短步数。

现在，你需要编写一个程序，输入一个由数字 $0$ 和 $1$ 组成的迷宫，以及起点集合和终点集合的坐标，输出走这个迷宫最少需要多少步。

题目保证起点和终点一定在空地上，并且保证问题有解。

下标从 0 开始

输入格式

第一行两个整数 $n, m$，分别表示 有 $n$ 行 $m$ 列

接下来是由 $1$ 和 $0$ 组成的 $n \times m$ 阵列，表示 迷宫 的具体情况

第 $n+2$ 行，是 $1$ 个整数 s，表示起点集合中起点的个数，接下去的 $s$ 行，每行两个整数分别表示起点在迷宫中的位置。

第 $n+2+s+1$ 行，是 $1$ 个整数 e, 表示终点集合中终点的个数，接下去的 e 行，每行两个整数分别表示终点在迷宫中的位置。

输出格式

一个整数，表示走出迷宫最少的步数。

样例 #1

样例输入 #1

7 7
0 0 0 0 0 0 0
1 0 0 1 0 0 0
0 0 1 0 1 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 1 0 1
0 1 0 0 0 0 0
3
2 5
4 2
3 4
2
0 5
3 0

样例输出 #1

2

提示

$s, e \leq 10000$

$s \times e \leq 200000$