P13951 [ICPC 2023 Nanjing R] Cool, It's Yesterday Four Times More

After the great success in 2018, 2019, 2020, 2021 and 2022, Nanjing University of Aeronautics and Astronautics (NUAA) will host the $\textit{International Collegiate Programming Contest}$ (ICPC) Nanjing regional for the sixth 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. This year, there are around $330$ teams participating in the contest. There are at most $33$ gold medals, $66$ silver medals and $99$ bronze medals that will be awarded (note that these numbers are for reference only). We are looking forward to seeing participants' outstanding performance! What's even better is that, as the pandemic has come to an end, we can finally gather in Nanjing to participate in this wonderful contest. We'd like to be grateful 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}  The 2018 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 button 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 are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^3$, $1 \le n \times m \le 10^3$) indicating the number of rows and columns of the grid. For the following $n$ lines, the $i$-th line contains a string $s_{i, 1}s_{i, 2} \cdots s_{i, m}$ of length $m$ where each character is either $\texttt{.}$ (dot, ascii: 46) or $\texttt{O}$ (capitalized letter, ascii: 79). If $s_{i, j}$ is a $\texttt{.}$ then grid $(i, j)$ is empty; If $s_{i, j}$ is a $\texttt{O}$ then grid $(i, j)$ is a hole. It's guaranteed that the sum of $n \times m$ of all test cases will not exceed $5 \times 10^3$.

For each test case output one line containing one integer indicating the number of kangaroos for which there exists a sequence of operations to make it the winner.

The sample test cases are explained below. We use `W` to indicate the kangaroo which later becomes winner and `K` to indicate the other kangaroos. For the first sample test case, kangaroos initially located at $(1, 4)$, $(1, 5)$ and $(2, 5)$ may become winners. Possible sequences of operations are shown as follows: :::align{center}  ::: For the second sample test case, as there is only one kangaroo, no operation is needed for it to become the winner. For the third sample test case, as any operation will remove the two kangaroos at the same time, there is no possible winner. For the fourth sample test case, as there is no kangaroo, there is no possible winner.