/ OIer TK / 题库 /

胜利大逃亡

胜利大逃亡

测试数据来自 system/1175

描述

一个探险家,在一个山洞里发现了一大笔宝藏,但他不慎碰到了自毁开关,来时的道路损坏并且在一定时间内整个山洞将塌毁,因此他不得不通过一个住满吸血蝙蝠的迷宫,故事从这里开始了。

在这个m列n行的迷宫中,有p个石柱,另有b只吸血蝙蝠。

蝙蝠分三种类型:
① 当蝙蝠前方遇到石柱或墙,向左转。

② 当蝙蝠前方遇到石柱或墙,向后转。

③ 当蝙蝠前方遇到石柱或墙,向右转。

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

现在有一个人从(1,1)逃到(m,n),仅有(m+n-1)单位的时间,问在(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

样例1

样例输入1

3 3
1
1 2
1
2 3 1 1

样例输出1

3

提示

图片

来源

huyichen

信息

ID
1168
难度
9
分类
动态规划 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者