#6388. 「THUPC2018」赛艇 / Citing

内存限制:2048 MiB 时间限制:12000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

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 ,仅由字母 wasd 构成,从前往后第 i 个字符 s_i 表示对方在第 i 轮中,对方赛艇向上/左/下/右移动一个单位距离。

输出格式

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

样例

样例输入

5 6 5
000000
001001
000100
001000
000001
dwdaa

样例输出

4

样例解释

path.png

上图显示了路径序列可视化之后的结果,下图用蓝色标出了此时对方赛艇可能的位置。

location.png

数据范围与提示

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。