[BeiJing2016]空袭

时间限制：1s 空间限制：256MB

题目描述

空袭，又名空中打击，是在复杂地形中常见的一种远距支援打击手段。通常由侦察兵对目标进行指示，之后最近的

友方空中支援机将会发射一枚导弹打击目标。空袭拥有灵活性强，杀伤力大，丢失率严重等特点。导弹从发射到命

中需要一定的时间，因此对于移动单位而言打中非常困难。因此，有经验的友军空中支援部队将会预判目标单位的

移动方式，并对估计到达时的位置(而不是目标的当前位置)进行打击。现在我军侦察兵GloryKen正在练习如何空袭

打击一只“嗜血猎食者”（又称“三级狗”）。这种敌方单位移动速度快且不规律，通常是侦察兵的天敌，但空袭

只需一发即可消灭一只“三级狗”。地形可以看作是N×M的网格，有些格子有障碍无法通行。在空地上有一个敌方

单位“三级狗”。在接下来的一段时间内，侦察兵GloryKen将会对它进行若干次空袭。具体过程可以按回合制来描

述。三级狗的初始位置在坐标(x,y)，面向上下左右的某个方向。

每个回合由如下几个阶段组成。

1. GloryKen发出一次“空袭指示”，友军空中支援部队立即发射一枚导弹。这颗导弹将会在ai个回合之后命中三

级狗当前位置前方ai格的格子（这里的“前方”是指三级狗当前面向的方向。）。如果这个位置在地图外，那么此

次空袭失效。

2. 三级狗进行一次“移动”。它可以向上下左右移动一格（不能越界，也不能到达有障碍存在的格子），也可以

选择呆在当前的格子。如果进行移动，它的朝向将会变为移动的方向，否则它的朝向不变。

3. 之前所有预定于该回合到达的导弹全部同时到达在预定的位置，如果三级狗被导弹命中，它将立即死亡。导弹

不会对地形造成影响，即不会破坏障碍，也不会制造障碍。

现在，GloryKen想知道，T个回合的空袭之后，如果这只三级狗还存活，它的位置可能在哪里。于是，你需要求出

，对于每一个格子，这只三级狗有多少种方案能够在第T回合恰好到达这个格子，并且存活。两个方案不同，当且

仅当某个回合三级狗的移动选择不同。

输入格式

第一行三个数，N，M，T，表示网格大小以及回合数。接下来N行，每行M个字符，描述整张地图：

.表示一个空地;

*表示一个障碍;

一个数字(0,1,2,3其中之一)表示三级狗的位置，全图只有一个数字，且出现数字的位置是空地。这个数字说明了

三级狗的朝向：

0表示沿该方向走1步会导致x坐标+1

1表示沿该方向走1步会导致y坐标+1

2表示沿该方向走1步会导致x坐标-1

3表示沿该方向走1步会导致y坐标-1

接下来T-1行，每行一个数ai，表示空袭导弹将会在ai回合之后命中三级狗当前位置前方ai格的格子。显然第T回合

的空袭是没有意义的，因此输入不包含第T回合空袭的信息。

1≤N,M≤20，1≤ai≤12，1≤T≤50

输出格式

共N行，每行M个数，相邻两个数之间用一个空格分隔，表示三级狗恰好在第T回合到达这个格子并且存活的方案数(

虽然有障碍的点答案一定是0，但是为了整齐也请你输出这个值)。为了避免高精度，请将所有的答案对1000000007

取模后再输出。

样例输入

3 2 2
1.
*.
..
1

样例输出

2 0
0 1
0 0
初始时三级狗在(1,1)，向右。第一回合第一阶段：空袭将在1回合后(第2回合)打击三级狗面前的1格(即(1,2)格子
)。第一回合第二阶段：三级狗可以选择不动(1, 1,右)或者向前(1, 2,右)。第一回合第三阶段：没有导弹到达。
第二回合第一阶段：这是最后一回合，空袭没有意义。第二回合第二阶段：三级狗移动。如果之前选择不动(1, 1,
右)，三级狗可以选择继续不动(1, 1,右)或者向前(1, 2,右)。如果之前选择向前(1, 2,右)，三级狗可以选择不动
(1, 2,右)或者向左(1,1,左)或者向下(2, 2,下)。第二回合第三阶段：空袭在(1,2)到达，如果此时三级狗在(1,2)
，它将被杀死。综上，三级狗有两种方案在第二回合结束时在(1,1)并存活，有1种方案在第二回合结束时在(2,2)
存活。

提示

没有写明提示

题目来源

没有写明来源