题目描述
zth最近很喜欢给别人出迷宫题,他会给出一个N*M的迷宫,其中有T个障碍,并给定起点终点坐标。每次只能向相邻的(上下左右四个方向距离为1的方格)方格移动。zth想知道,最少需要多少次移动可以通过他的迷宫。
输入
每个样例第一行包含三个整数N、M和T。第二行包含四个整数,分别代表起点坐标SX,SY,终点坐标FX,FY。接下来T行,每行为障碍点的坐标。所有坐标均从1开始。
2 <= N, M <= 500, 0 <= T <= N * M - 2, 1 <= SX, FX <= N, 1 <= SY, FY <= M
输出
输出一行,包含一个整数,表示最短的路径距离,若没有可行路径,则输出-1