{"problem":{"name":"[蓝桥杯 2023 省 B] 岛屿个数","description":{"content":"小蓝得到了一副大小为 $M \\times N$ 的格子地图，可以将其视作一个只包含字符 `0`（代表海水）和 `1`（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 `1` 相连接而形成。 在岛屿 $A$ 所占据的格子中，如果可以从中选出 $k$ 个不同的格子，使得他们的坐标能够组成一个这样的排列：$\\left(x_{0},y_{0}\\right),","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9243"},"statements":[{"statement_type":"Markdown","content":"小蓝得到了一副大小为 $M \\times N$ 的格子地图，可以将其视作一个只包含字符 `0`（代表海水）和 `1`（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 `1` 相连接而形成。\n\n在岛屿 $A$ 所占据的格子中，如果可以从中选出 $k$ 个不同的格子，使得他们的坐标能够组成一个这样的排列：$\\left(x_{0},y_{0}\\right),\\left(x_{1},y_{1}\\right),\\ldots,\\left(x_{k-1},y_{k-1}\\right)$，其中 $\\left(x_{(i+1) \\bmod k},y_{(i+1) \\bmod k}\\right)$ 是由 $\\left(x_{i},y_{i}\\right)$ 通过上/下/左/右移动一次得来的（$0 \\leq i \\leq k-1$），此时这 $k$ 个格子就构成了一个「环」。如果另一个岛屿 $B$ 所占据的格子全部位于这个「环」内部，此时我们将岛屿 $B$ 视作是岛屿 $A$ 的子岛屿。若 $B$ 是 $A$ 的子岛屿，$C$ 又是 $B$ 的子岛屿，那 $C$ 也是 $A$ 的子岛屿。\n\n请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。\n\n## Input\n\n第一行一个整数 $T$，表示有 $T$ 组测试数据。\n\n接下来输入 $T$ 组数据。对于每组数据，第一行包含两个用空格分隔的整数 $M, N$ 表示地图大小；接下来输入 $M$ 行，每行包含 $N$ 个字符，字符只可能是 `0` 或 `1`。\n\n## Output\n\n对于每组数据，输出一行，包含一个整数表示答案。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：\n```\n01111\n11001\n10201\n10001\n11111\n```\n岛屿 2 在岛屿 1 的「环」内部，所以岛屿 2 是岛屿 1 的子岛屿，答案为 $1$。\n\n对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：\n```\n111111\n100001\n020301\n100001\n111111\n```\n注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿，因为岛屿 1 和岛屿 2 中均没有「环」。\n\n**【评测用例规模与约定】**\n\n对于 $30 \\%$ 的评测用例，$1 \\leq M,N \\leq 10$。\n\n对于 $100 \\%$ 的评测用例，$1 \\leq T \\leq 10$，$1 \\leq M,N \\leq 50$ 。  \n\n蓝桥杯 2023 省赛 B 组 F 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9243","tags":["搜索","2023","蓝桥杯省赛"],"sample_group":[["2\n5 5\n01111\n11001\n10101\n10001\n11111\n5 6\n111111\n100001\n010101\n100001\n111111\n","1\n3"]],"created_at":"2026-03-03 11:09:25"}}