#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 项铜奖(数字仅供参考)。让我们期待选手的表现,也感谢组委会、工作人员和志愿者的付出!

2018 年的 K 题 Kangaroo Puzzle 要求为下述游戏构造操作序列:网格有 行 列(),一些格子是墙,其余格子是空地,每个空地最初都有一只袋鼠,至少有两只袋鼠。袋鼠可在上、下、左、右相邻空地之间移动。玩家按下 U、D、L、R,所有袋鼠同时按照该方向移动。选手需要构造至多 次操作,使袋鼠聚集到同一格。
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 年,袋鼠题又回来了。本次需要解决的问题如下。
给定一个 行 列的网格。有些格子是墙,其余格子是空地。每个空地最初都有一只袋鼠。 所有袋鼠同时按照按键移动。对于位于第 行、第 列的袋鼠:
U:若 且 不是墙,移动到 ,否则留在原地。D:若 且 不是墙,移动到 ,否则留在原地。L:若 且 不是墙,移动到 ,否则留在原地。R:若 且 不是墙,移动到 ,否则留在原地。
给定一个仅由 U、D、L、R 组成的长度为 的操作序列 ,按照这个序列无限循环操作:前 次操作依次是 ,第 次操作与第 次操作相同。
对于每个 ,求最小的非负整数 ,使执行 次操作后,最多有 个格子含有袋鼠。如果永远无法达到,输出 。
袋鼠可以同时处在同一格中;统计的是含有袋鼠的格子数,而不是袋鼠总数。
输入格式
每个输入文件只有一组测试数据。
第一行三个整数 ,满足 ,,。
第二行一个长度为 的字符串,表示操作序列。
接下来 行,每行一个长度为 的二进制字符串。字符 1 表示空地,字符 0 表示墙。保证至少有一个空地。
输出格式
输出 行,第 行输出 ;如果不可能达到,输出 。
样例 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