P9243 [Lanqiao Cup 2023 NOI Qualifier B] Number of Islands

Xiao Lan obtained a grid map of size $M \times N$. It can be viewed as a 2D array containing only the characters `0` (sea) and `1` (land). Outside the map, everything can be considered sea. Each island is formed by connecting adjacent `1` cells in the four directions up, down, left, and right. On the cells occupied by island $A$, if we can choose $k$ distinct cells such that their coordinates can form an ordering $\left(x_{0},y_{0}\right),\left(x_{1},y_{1}\right),\ldots,\left(x_{k-1},y_{k-1}\right)$, where $\left(x_{(i+1) \bmod k},y_{(i+1) \bmod k}\right)$ is obtained from $\left(x_{i},y_{i}\right)$ by moving exactly once up/down/left/right ($0 \leq i \leq k-1$), then these $k$ cells form a “cycle”. If all cells occupied by another island $B$ are located strictly inside this “cycle”, then we consider island $B$ to be a sub-island of island $A$. If $B$ is a sub-island of $A$, and $C$ is a sub-island of $B$, then $C$ is also a sub-island of $A$. How many islands are there on this map? When counting, you do not need to count the number of sub-islands.

The first line contains an integer $T$, meaning there are $T$ sets of testdata. Then follow $T$ test cases. For each test case, the first line contains two integers $M, N$ separated by spaces, indicating the map size. Then $M$ lines follow, each containing $N$ characters, and each character is only `0` or `1`.

For each test case, output one line containing one integer, which is the answer.

**Sample Explanation** For the first test case, there are two islands, distinguished by different digits below: ``` 01111 11001 10201 10001 11111 ``` Island 2 is inside the “cycle” of island 1, so island 2 is a sub-island of island 1. The answer is $1$. For the second test case, there are three islands, distinguished by different digits below: ``` 111111 100001 020301 100001 111111 ``` Note that island 3 is not a sub-island of island 1 or island 2, because neither island 1 nor island 2 has a “cycle”. **Constraints** For $30\%$ of the test cases, $1 \leq M, N \leq 10$. For $100\%$ of the test cases, $1 \leq T \leq 10$, $1 \leq M, N \leq 50$. Lanqiao Cup 2023 Provincial Contest B Group, Problem F. Translated by ChatGPT 5