题目理解

这是一个在 $n \times m$ 网格上的回合制游戏：

• 初始有一些白色格子（至少一个）
• 玩家轮流将白色格子染黑
• 失败条件：
  1. $(1,1)$ 或 $(n,m)$ 变成黑色
  2. $(1,1)$ 和 $(n,m)$ 不在同一个白色四连通块中

我们需要判断在双方都采取最优策略时，先手（小 I）是否会获胜。

---

问题分析

关键观察

这是一个图上的删点游戏，但带有特殊约束：

• 必须保持 $(1,1)$ 和 $(n,m)$ 的白色连通性
• 这两个关键格子必须始终保持白色

这实际上是在白色格子的连通分量上进行游戏。

---

代码解法详解

1. 连通性检查

bool check() {
    if (s[1][1] == 'B') return 0;  // 起点已经是黑色
    
    // BFS检查(1,1)和(n,m)是否在同一个白色连通块
    queue<pii> que;
    v[1][1] = c, que.push({1, 1});
    
    while (!que.empty()) {
        auto [x, y] = que.front(); que.pop();
        for (int d = 0; d < 4; d++) {
            int xx = x + dx[d], yy = y + dy[d];
            if (!xx || !yy || xx > n || yy > m || 
                s[xx][yy] == 'B' || v[xx][yy] == c) 
                continue;
                
            if (xx == n && yy == m) return 1;  // 到达终点
            
            v[xx][yy] = c, que.push({xx, yy});
        }
    }
    return 0;
}

这个函数检查初始状态下 $(1,1)$ 和 $(n,m)$ 是否连通。

2. 胜负判断逻辑

void sol() {
    cin >> n >> m, ++c;
    for (int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);
    
    // 情况1：初始就不连通
    if (!check()) {
        puts("J");  // 先手直接输
        return;
    }
    
    // 情况2：初始连通，根据奇偶性判断
    int sm = n + m;
    for (int i = 1; i <= n; i++)
        sm += count(s[i] + 1, s[i] + m + 1, 'W');
    
    puts(sm & 1 ? "J" : "I");
}

---

算法正确性分析

情况1：初始不连通

如果 $(1,1)$ 和 $(n,m)$ 一开始就不在同一个白色连通块中，那么：

• 先手小 I 必须移动（规则要求）
• 无论染黑哪个白色格子，都会破坏某个连通分量
• 但游戏已经处于失败状态，所以先手直接输

情况2：初始连通

代码使用了一个巧妙的奇偶性判断：

int sm = n + m + (白色格子总数)

然后检查 sm 的奇偶性：

• 奇数：后手（小 J）必胜
• 偶数：先手（小 I）必胜

为什么这样判断？

这实际上是在计算一个关键路径+白色格子的奇偶性：

• $n + m$ 是 $(1,1)$ 到 $(n,m)$ 的最短曼哈顿距离
• 加上白色格子总数，得到一个与游戏状态相关的奇偶值
• 这个值决定了最优策略下的胜负关系

---

样例分析

样例1

2×2网格：
WB
WW

白色格子：3个
n+m = 2+2 = 4
sm = 4 + 3 = 7 (奇数) → 输出 J

样例2

2×2网格：
WW
WW

白色格子：4个
n+m = 2+2 = 4
sm = 4 + 4 = 8 (偶数) → 输出 I

与题目给出的输出一致。

---

复杂度分析

• 连通性检查：$O(nm)$ 使用 BFS
• 白色格子计数：$O(nm)$
• 总复杂度：$O(T \cdot nm)$，满足 $T \cdot nm \le 5\times 10^6$ 的限制

---

算法标签

• 图论/连通性
• 博弈论
• BFS搜索
• 奇偶性分析
• 组合游戏

---

总结

这道题的解法核心是：

1. 连通性验证：首先检查游戏是否已经处于失败状态
2. 奇偶性判断：通过计算 $n + m + \text{白色格子数}$ 的奇偶性决定胜负
3. 最优策略：在保持连通性的前提下，双方会采取最优的删点顺序

这种解法巧妙地利用了网格图的特性和奇偶性，避免了复杂的博弈树分析。