#P18211. Hey, Have You Seen My Kangaroo?

Hey, Have You Seen My Kangaroo?

Hey, Have You Seen My Kangaroo?

继 2018、2019、2020、2021、2022 和 2023 年成功承办赛事后,南京航空航天大学(NUAA)将连续第七年承办 ICPC 南京区域赛。

2018 与 2019 年,“中二之力”和“三个顶俩”为清华大学赢得冠军。2020、2021 与 2022 年,北京大学的“逆十字”获得三连冠。2023 年,北京大学的“重生之我是菜狗”获得冠军;他们还获得第 46 届 ICPC 世界总决赛冠军,在 13 年后为 EC 赛区重新赢回奖杯。

今年约有 335 支队伍参加南京站,预计颁发至多 33 项金奖、66 项银奖和 99 项铜奖(数字仅供参考)。让我们期待选手的表现,也感谢组委会、工作人员和志愿者的付出!

2023 ICPC 亚洲区域赛南京站照片

2018 年的 K 题 Kangaroo Puzzle 要求为下述游戏构造操作序列:网格有 nn 行 mm 列(1≤n,m≤201\le n,m\le20),一些格子是墙,其余格子是空地,每个空地最初都有一只袋鼠,至少有两只袋鼠。袋鼠可在上、下、左、右相邻空地之间移动。玩家按下 U、D、L、R,所有袋鼠同时按照该方向移动。选手需要构造至多 5×1045\times10^4 次操作,使袋鼠聚集到同一格。

2020 年的 A 题 Ah, It's Yesterday Once More 要求构造一张地图,证明下面的程序不能解决上述问题:

#include <bits/stdc++.h>
using namespace std;
string s = "UDLR";
int main() {
    srand(time(NULL));
    for (int i = 1; i <= 50000; i++)
        putchar(s[rand() % 4]);
    return 0;
}

2021、2022、2023 年的 A 题 Oops, It's Yesterday Twice More、Stop, Yesterday Please No More、Cool, It's Yesterday Four Times More,也都是袋鼠题!如果每年都介绍所有往年的题,到了 3024 年可能会有一道题拥有 500 页题面,所以这里就省略了;你也可能已经在热身赛里见过它们。

2024 年,袋鼠题又回来了。本次需要解决的问题如下。

给定一个 nn 行 mm 列的网格。有些格子是墙,其余格子是空地。每个空地最初都有一只袋鼠。 所有袋鼠同时按照按键移动。对于位于第 ii 行、第 jj 列的袋鼠:

  • U:若 i>1i>1 且 (i−1,j)(i-1,j) 不是墙,移动到 (i−1,j)(i-1,j),否则留在原地。
  • D:若 i<ni<n 且 (i+1,j)(i+1,j) 不是墙,移动到 (i+1,j)(i+1,j),否则留在原地。
  • L:若 j>1j>1 且 (i,j−1)(i,j-1) 不是墙,移动到 (i,j−1)(i,j-1),否则留在原地。
  • R:若 j<mj<m 且 (i,j+1)(i,j+1) 不是墙,移动到 (i,j+1)(i,j+1),否则留在原地。

给定一个仅由 U、D、L、R 组成的长度为 kk 的操作序列 s1s2…sks_1s_2\ldots s_k,按照这个序列无限循环操作:前 kk 次操作依次是 s1,…,sks_1,\ldots,s_k,第 t>kt>k 次操作与第 t−kt-k 次操作相同。

对于每个 1≤i≤nm1\le i\le n m,求最小的非负整数 viv_i,使执行 viv_i 次操作后,最多有 ii 个格子含有袋鼠。如果永远无法达到,输出 −1-1。

袋鼠可以同时处在同一格中;统计的是含有袋鼠的格子数,而不是袋鼠总数。

输入格式

每个输入文件只有一组测试数据。

第一行三个整数 n,m,kn,m,k,满足 1≤n,m≤2×1051\le n,m\le2\times10^5,1≤nm≤2×1051\le nm\le2\times10^5,1≤k≤2001\le k\le200。

第二行一个长度为 kk 的字符串,表示操作序列。

接下来 nn 行,每行一个长度为 mm 的二进制字符串。字符 1 表示空地,字符 0 表示墙。保证至少有一个空地。

输出格式

输出 nmnm 行,第 ii 行输出 viv_i;如果不可能达到,输出 −1-1。

样例 1

输入:

3 3 6
ULDDRR
010
111
010

输出:

-1
4
2
1
0
0
0
0
0

样例 2

输入:

3 3 6
ULDDRR
010
111
011

输出:

7
4
2
1
1
0
0
0
0

样例 3

输入:

1 5 1
R
11111

输出:

4
3
2
1
0