题目内容

某运营商需要在某一区域铺设光缆，起点为机房，终点为某小区，整个区域以一个 m×n 的矩阵表示，光缆沿着矩阵的边铺设（不允许走对角线），区域内有些节点可以经过，但有些节点（如图红色的位置，输入时给定）因为各种因素无法经过。起点的机房与终点的小区可能在区域内的任何位置，计算从机房到目标小区铺设光缆的最短距离（如果光缆无法从起点机房铺设到达目标小区，返回 -1）。

输入描述

m矩阵宽(横轴点数量，例如图示为11，以0~10作为下标)

n矩阵高(纵轴点数量，例如图示为8，以0~7作为下标)

机房坐标(a1,a2)

目标小区坐标(b1,b2)

矩阵内不允许经过的节点数量k

依次为这些不允许经过的节点坐标

1 <= m,n <= 1000

0 <=k <= 100000

输出描述

从机房到目标小区铺设光缆的最短距离

样例1

输入

11
8
2 3
7 5
6
2 4
3 5
4 4
5 4
6 4
7 4

输出

9

说明
11*8的矩阵(横轴坐标0~10，纵轴坐标0~7)

起始点(机房)为坐标(2 3)

目标点(要连到的小区)为坐标(7 5)

矩阵内不允许经过的节点数为6个

依次给出这些不允许经过的节点坐标

样例2

输入

3
3 
0 0
2 2
3
0 1
1 1
2 1

输出

-1

说明
3×3 的矩阵

起始点（机房）为坐标 (0,0)

目标点（小区）为坐标 (2,2)

矩阵内不允许经过的节点数为 3 个

依次给出这些不允许经过的节点坐标