[THUPC2018] 赛艇

题目描述

Lavender、Caryophyllus、Jasmine、Dianthus现在在玩一款名叫“赛艇”的游戏。 这个游戏的规则是这样的: 1. 玩家自由组成两队,一个人当赛艇的艇长,另一个人当侦察兵; 2. 每次游戏开始时,双方均拥有由系统生成的某张地图,该地图以01矩阵的形式表示,`1`表示有障碍物,无法通行,`0`表示水域空旷,可以通行; 3. 第一回合,双方的赛艇艇长都要在地图上指定一个出发点,该出发点不能是障碍物,也就是只能为`0`; 4. 在每个回合中,艇长可以指挥自己的赛艇向上/下/左/右四个方向的某一方向的空旷水域移动一个单位的距离,也就是说只能移向四个方向上的某个`0`上(当然,不能移动出地图之外);在该操作完成之后,**必须向对方说出自己在该回合移动的方向**; 5. 双方的侦察兵负责记录每一回合对方赛艇的移动方向,并负责推断此时对方赛艇可能的位置;如果某方的侦察兵推测出对方赛艇此时的精确位置,那么可以向其发射导弹,该侦察兵所在的一方胜利; 现在,Jasmine记录了一些对方赛艇的路径,她想确定一下此时对方所有可能的位置共有几种。由于她不是很擅长计算,所以这个任务就交给你了。

输入输出格式

输入格式


输入第一行包含三个正整数 $n$,$m$,$k$,分别表示地图为 $n$ 行 $m$ 列,当前游戏已经进行了 $k$ 轮。保证 $2\le n,m \le 1500$,$1\le k\le 5\times 10^6$。 输入第二行到第 $n+1$ 行为一个 $n$ 行 $m$ 列的 01 矩阵,无任何分隔符号,表示地图的具体信息,具体含义如上所示。 输入的最后一行为一个长度为 $k$ 的字符串 $s$,仅由字母 `w`、`a`、`s`、`d` 构成,从前往后第 $i$ 个字符 $s_i$ 表示对方在第 $i$ 轮中,对方赛艇向上/左/下/右移动一个单位距离。

输出格式


输出一行一个正整数,表示在第 $k$ 轮游戏回合的时候,对方赛艇可能的位置的种数。对于所有输入数据,**保证有合法解**。

输入输出样例

输入样例 #1

5 6 5
000000
001001
000100
001000
000001
dwdaa

输出样例 #1

4

说明

### 样例解释 ![](https://i.loli.net/2018/05/14/5af98ebcd79df.png) 上图显示了路径序列可视化之后的结果,下图用蓝色标出了此时对方赛艇可能的位置。 ![](https://i.loli.net/2018/05/14/5af98ed39a602.png) ### 版权信息 来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。 题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。