You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

​ 给定一个n*m方格的迷宫，迷宫里有t处障碍，障碍处不可通过。给定起点和终点坐标，问每个方格最多经过1次，在迷宫中移动有上下左右四种方式。保证起点上没有障碍。问从起点到终点的最短路径长度是多少？如果不存在起点到终点的路径，则输出-1。

输入格式

第一行n,m和t,n为行，m为列，t为障碍总数。（1<=n*m<=1000）。

第二行起点坐标sx,sy,终点坐标fx,fy。

接下来t行，每行为障碍的坐标。

输出格式

如果存在解答，则：

第一行输出最短路径的长度k(起点终点也算在步数内)否则输出-1.

样例 #1

样例输入 #1

2 2 1
1 1 2 2
1 2

样例输出 #1

3