#P5447. [THUPC2018] 赛艇

[THUPC2018] 赛艇

题目描述

Lavender、Caryophyllus、Jasmine、Dianthus现在在玩一款名叫“赛艇”的游戏。

这个游戏的规则是这样的:

  1. 玩家自由组成两队,一个人当赛艇的艇长,另一个人当侦察兵;
  2. 每次游戏开始时,双方均拥有由系统生成的某张地图,该地图以01矩阵的形式表示,1表示有障碍物,无法通行,0表示水域空旷,可以通行;
  3. 第一回合,双方的赛艇艇长都要在地图上指定一个出发点,该出发点不能是障碍物,也就是只能为0
  4. 在每个回合中,艇长可以指挥自己的赛艇向上/下/左/右四个方向的某一方向的空旷水域移动一个单位的距离,也就是说只能移向四个方向上的某个0上(当然,不能移动出地图之外);在该操作完成之后,必须向对方说出自己在该回合移动的方向
  5. 双方的侦察兵负责记录每一回合对方赛艇的移动方向,并负责推断此时对方赛艇可能的位置;如果某方的侦察兵推测出对方赛艇此时的精确位置,那么可以向其发射导弹,该侦察兵所在的一方胜利;

现在,Jasmine记录了一些对方赛艇的路径,她想确定一下此时对方所有可能的位置共有几种。由于她不是很擅长计算,所以这个任务就交给你了。

输入格式

输入第一行包含三个正整数 nnmmkk,分别表示地图为 nnmm 列,当前游戏已经进行了 kk 轮。保证 2n,m15002\le n,m \le 15001k5×1061\le k\le 5\times 10^6

输入第二行到第 n+1n+1 行为一个 nnmm 列的 01 矩阵,无任何分隔符号,表示地图的具体信息,具体含义如上所示。

输入的最后一行为一个长度为 kk 的字符串 ss,仅由字母 wasd 构成,从前往后第 ii 个字符 sis_i 表示对方在第 ii 轮中,对方赛艇向上/左/下/右移动一个单位距离。

输出格式

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

5 6 5
000000
001001
000100
001000
000001
dwdaa
4

提示

样例解释

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

版权信息

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

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