P14014 [ICPC 2024 Nanjing R] Hey, Have You Seen My Kangaroo?

$\textbf{Please note the UNUSUAL MEMORY LIMIT of this problem.}$ After the great success in 2018, 2019, 2020, 2021, 2022, and 2023, the Nanjing University of Aeronautics and Astronautics (NUAA) will host the $\textit{International Collegiate Programming Contest}$ (ICPC) Nanjing regional for the seventh time in a row. Team $\textbf{\textit{Power of Two}}$ and team $\textbf{\textit{Three Hold Two}}$ won the champion title for Tsinghua University in 2018 and 2019. In 2020, 2021, and 2022, team $\textbf{\textit{Inverted Cross}}$ from Peking University won the three-peat champion titles. In 2023, another team $\textbf{\textit{Reborn as a Vegetable Dog}}$ from Peking University won the title. They also won the 46th ICPC World Champion, reclaiming the trophy for the EC region after 13 years! This year, around $335$ teams are participating in the contest. At most $33$ gold medals, $66$ silver medals, and $99$ bronze medals will be awarded (note that these numbers are for reference only). We are looking forward to seeing the participants' outstanding performance! We also want to express our gratitude for the hard work done by all staff and volunteers for this contest. Thank you all for your great contribution to this contest! :::align{center}  Photo taken in the 2023 ICPC Asia Nanjing Regional Contest ::: In the 2018 contest, problem K, $\textbf{\textit{Kangaroo Puzzle}}$, requires the contestants to construct an operation sequence for the game: > The puzzle is a grid with $n$ rows and $m$ columns ($1 \le n, m \le 20$), and there are some (at least $2$) kangaroos standing in the puzzle. The player's goal is to control them to get together. There are some walls in some cells, and the kangaroos cannot enter the cells with walls. The other cells are empty. The kangaroos can move from an empty cell to an adjacent empty cell in four directions: up, down, left, and right. > There is exactly one kangaroo in every empty cell in the beginning, and the player can control the kangaroos by pressing the buttons U, D, L, R on the keyboard. The kangaroos will move simultaneously according to the button you press. > The contestant needs to construct an operating sequence of at most $5 \times 10^4$ steps consisting of U, D, L, R only to achieve the goal. In the 2020 contest, problem A, $\textbf{\textit{Ah, It's Yesterday Once More}}$, requires the contestants to construct an input map to hack the following code of the problem described before: ```cpp #include using namespace std; string s = "UDLR"; int main() { srand(time(NULL)); for (int i = 1; i

There is only one test case in each test file. The first line contains three integers $n$, $m$, and $k$ ($1 \le n, m \le 2 \times 10^5$, $1 \le n \times m \le 2 \times 10^5$, $1 \le k \le 200$), indicating the number of rows and columns of the grid, and the length of the operating sequence. The second line contains a string $s_1 s_2 \cdots s_k$ ($s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$), indicating the operating sequence. For the following $n$ lines, the $i$-th line contains a binary string $a_{i,1}a_{i,2}\cdots a_{i,m}$ ($a_{i,j} \in \{\text{`0'}, \text{`1'}\}$). If $a_{i,j} = \text{`1'}$ then cell $(i, j)$ is empty; Otherwise if $a_{i,j} = \text{`0'}$ then cell $(i, j)$ is blocked and cannot be entered. It is guaranteed that there is at least one empty cell in the grid.

Output $n \times m$ lines, where the $i$-th line contains an integer $v_i$, indicating the minimum number of operations needed so that at most $i$ cells will contain kangaroos. If this is impossible, just output $\texttt{-1}$ on this line.