石头游戏

Luogu
IDLGP10498
Time1000ms
Memory512MB
DifficultyP5
矩阵加速
石头游戏在一个 $n$ 行 $m$ 列的网格上进行,每个格子对应一种操作序列,操作序列至多有 $10$ 种,分别用 $0 \sim 9$ 这 $10$ 个数字指明。 操作序列是一个长度不超过 $6$ 且循环执行、每秒执行一个字符的字符串。 每秒钟,所有格子同时执行各自操作序列里的下一个字符。 序列中的每个字符是以下格式之一: 1. 数字 $0 \sim 9$:表示拿 $0 \sim 9$ 个石头到该格子。 2. `NWSE`:表示把这个格子内所有的石头推到相邻的格子,`N` 表示上方,`W` 表示左方,`S` 表示下方,`E` 表示右方。 3. `D`:表示拿走这个格子的所有石头。 给定每种操作序列对应的字符串,以及网格中每个格子对应的操作序列,求石头游戏进行了 $t$ 秒之后,石头最多的格子里有多少个石头。 在游戏开始时,网格是空的。 ## Input 第一行 $4$ 个整数 $n, m, t, act$。 接下来 $n$ 行,每行 $m$ 个字符,表示每个格子对应的操作序列。 最后 $act$ 行,每行一个字符串,表示从 $0$ 开始的每个操作序列。 ## Output 一个整数:游戏进行了 $t$ 秒之后,所有方格中石头最多的格子有多少个石头。 [samples] ## Note 对于所有的测试数据, 满足 $1 \le m,n \le 8$,$1 \le t \le 10^8$,$1 \le act \le 10$。
Samples
Input #1
1 6 10 3
011112
1E
E
0
Output #1
3
API Response (JSON)
{
  "problem": {
    "name": "石头游戏",
    "description": {
      "content": "石头游戏在一个 $n$ 行 $m$ 列的网格上进行,每个格子对应一种操作序列,操作序列至多有 $10$ 种,分别用 $0 \\sim 9$ 这 $10$ 个数字指明。 操作序列是一个长度不超过 $6$ 且循环执行、每秒执行一个字符的字符串。 每秒钟,所有格子同时执行各自操作序列里的下一个字符。 序列中的每个字符是以下格式之一:   1. 数字 $0 \\sim 9$:表示拿 $0 \\sim 9",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10498"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "石头游戏在一个 $n$ 行 $m$ 列的网格上进行,每个格子对应一种操作序列,操作序列至多有 $10$ 种,分别用 $0 \\sim 9$ 这 $10$ 个数字指明。\n\n操作序列是一个长度不超过 $6$ 且循环执行、每秒执行一个字符的字符串。\n\n每秒钟,所有格子同时执行各自操作序列里的下一个字符。\n\n序列中的每个字符是以下格式之一:\n\n  1. 数字 $0 \\sim 9$:表示拿 $0 \\sim 9...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments