2115: 宝典2第十一章胜利大逃亡

【题目描述】胜利大逃亡（escape.cpp/c/pas）

天顶星人设下了无数的陷阱，魔法世界的一支侦察小分队就落到了一个迷宫陷阱之中，现在，小分队要从一个m列n行的迷宫中逃走，有p个石柱，另有b只吸血蝙蝠。

　　蝙蝠分三种类型：

　　（１）当蝙蝠前方遇到石柱或墙，向左转。

（２）当蝙蝠前方遇到石柱或墙，向后转。

（３）当蝙蝠前方遇到石柱或墙，向右转。

　　人可以向上、下、左、右四个方向移动或在原位置等待，人运动一格或等待，都花费一个单位时间，在一个单位时间内，蝙蝠和人可以同时移动，蝙蝠也可以向上、下、左、右四个方向移动或旋转，注意旋转不花时间，也就是说蝙蝠和人都可以先旋转再移动。同一时刻，人和蝙蝠在同一地点时，人死亡。人和蝙蝠可以互相穿过，且蝙蝠可以重叠。

　　现在从（1，1）逃到（m，n），仅有（m+n－1）单位时间，问在该时间内共有几种逃亡路线。

　　注：在第1个时刻，人进入（1，1），蝙蝠赋初始状态，在第（m+n－1）时刻，人要到达（m，n）。

　　若初始状态中蝙蝠与石柱重合，则认为蝙蝠在石柱上休息，不会动。

【输入格式】

输入文件第1行为m，n；第2行为石柱个数p;以下p行，每行两个整数，分别为石柱的横、纵坐标；第p+3行，为蝙蝠数b；以下b行，每行四个整数，分别为蝙蝠的横、纵坐标，蝙蝠方向d(上为1，左为2，下为3，右为4)，以及蝙蝠类型t用1，2，3表示（2≤m≤100；2≤n≤100；0≤p≤100；0≤b≤100）。

【输出格式】

仅一行，为逃脱的方法数，若无解则输出0。

【输入样例】

3 3

1

1 2

1

2 3 1 1

【输出样例】

3