J8 习题-3 迷宫的走法总数

题目描述

一个 $N*M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。 给定起点坐标和终点坐标，问每个方格最多经过 $1$ 次，在迷宫中移动有上下左右四种方式（保证起点上没有障碍）。请编程求出从起点坐标到终点坐标的走法方案的总数。

输入格式

第一行三个整数 $N,M,T$，表示迷宫有 $N$ 行，$M$ 列，有 $T$ 个障碍。 第二行四个整数，分别表示起点坐标 $SX,SY$，终点坐标 $FX,FY$ 。 接下来 $T$ 行，表示障碍的坐标。

输出格式

一个整数，表示从起点坐标到终点坐标的方案总数。

样例输入

2 2 1
1 1 2 2
1 2

样例输出

1

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据有： $1 \leq N,M \leq 5$ 。