{"problem":{"name":"[THUPC 2024 决赛] 黑白","description":{"content":"小 I 和小 J 又在玩游戏。 游戏在一个 $n \\times m$ 的网格上进行，我们用二元组 $(x,y)$ 描述第 $x$ 行第 $y$ 列的格子，其中 $1 \\le x \\le n, 1 \\le y \\le m$。初始时，网格上有至少一个格子是白色的，其他格子是黑色的。 小 I 和小 J 轮流操作，小 I 先手。每次操作时，操作方必须选择恰好一个白色的格子并将其染黑。 称两个格子相邻","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10543"},"statements":[{"statement_type":"Markdown","content":"小 I 和小 J 又在玩游戏。\n\n游戏在一个 $n \\times m$ 的网格上进行，我们用二元组 $(x,y)$ 描述第 $x$ 行第 $y$ 列的格子，其中 $1 \\le x \\le n, 1 \\le y \\le m$。初始时，网格上有至少一个格子是白色的，其他格子是黑色的。\n\n小 I 和小 J 轮流操作，小 I 先手。每次操作时，操作方必须选择恰好一个白色的格子并将其染黑。\n\n称两个格子相邻当且仅当它们共用一条边。若某次操作后，格子 $(1,1)$ 不是白的，或者格子 $(n,m)$ 不是白的，或者无法从 $(1,1)$ 出发，每次经过相邻的白色格子，最终到达 $(n,m)$（即 $(1,1)$ 和 $(n,m)$ 不在同一个白色格子构成的四连通块内），则当前操作方输，另一方胜利。\n\n你作为游戏的观众，想知道在小 I 和小 J 绝顶聪明的情况下，谁会获胜。\n\n## Input\n\n**本题有多组测试数据。** 输入的第一行一个整数 $T (1 \\le T \\le 100)$ 表示测试数据组数，接下来依次输入每组测试数据。对于每组测试数据，\n\n- 第一行两个整数 $n, m (2 \\le n, m \\le 1000)$，表示网格的大小。\n- 接下来 $n$ 行每行一个长度为 $m$、字符集为 `BW` 的字符串，描述网格初始时的染色情况。其中第 $i$ 行第 $j$ 个字符为 `B` 表示 $(i,j)$ 初始为黑色，否则为 `W` 表示 $(i,j)$ 初始为白色。保证初始棋盘上至少有一个白色格子。\n\n保证单个测试点中所有测试数据的 $n \\times m$ 的和不超过 $5 \\times 10^6$。\n\n## Output\n\n对于每组测试数据输出一行一个字符，若小 I 必胜输出 `I`，否则若小 J 必胜输出 `J`。\n\n[samples]\n\n## Note\n\n对于第一组测试数据，小 I 只能染黑 $(2,1)$，但染黑 $(2,1)$ 会导致无法仅通过每次移动到相邻的白色格子从 $(1,1)$ 移动到 $(2,2)$，因此无论小 I 如何操作都将失败，故输出 `J`。\n\n对于第二组测试数据，小 I 可以染黑 $(1,2)$，然后无论小 J 如何操作都将失败，故输出 `I`。\n\n**来源与致谢**\n\n来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。\n\n数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10543","tags":["博弈论","2024","广度优先搜索 BFS","最短路","THUPC"],"sample_group":[["2\n2 2\nWB\nWW\n2 2\nWW\nWW\n","J\nI\n"]],"created_at":"2026-03-03 11:09:25"}}