Problem Description

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.

Input Format

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.

Output Format

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

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

1
3

Hint

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