B. Pushing Balls 详细题解

一、问题重述

有一个 $n \times m$ 的网格，初始为空。每次操作可以：

• 从某行的最左边缘推入一个球，该球会向右移动，遇到球则让原球继续右移，自己停下
• 从某列的最上边缘推入一个球，该球会向下移动，遇到球则让原球继续下移，自己停下

给定最终网格（$1$ 表示有球，$0$ 表示无球），判断是否能通过一系列操作达到该状态。

二、核心观察

2.1 操作的本质

• 从第 $i$ 行左边缘推球：相当于将第 $i$ 行最左边的 $0$ 变成 $1$，且该行该列右侧的球依次右移（但最终状态固定，我们只关心能否实现）
• 从第 $j$ 列上边缘推球：相当于将第 $j$ 列最上边的 $0$ 变成 $1$，且该列下方的球依次下移

关键：每次操作只能把某个行/列最前端的 $0$ 变成 $1$，不能凭空在中间产生 $1$。

2.2 逆向思考

从最终状态出发，逆向操作：

• 如果一个 $1$ 的上方全是 $1$ 或者左方全是 $1$，那么它可能是最后一次推球产生的（因为从左边或上边推球时，它挡住了后面的球）
• 逆向操作：将这样的 $1$ 变回 $0$，不会破坏可推性

重复此过程，如果能将所有 $1$ 消去，则原状态可达。

2.3 必要条件

对于任意一个 $1$，如果它的上方存在 $0$ 且左方也存在 $0$，那么这个 $1$ 永远无法通过任何正向操作产生：

• 从左边推球：只能把最左边 $0$ 变 $1$，无法跳过左边的 $0$ 去产生它
• 从上边推球：只能把最上边 $0$ 变 $1$，无法跳过上边的 $0$ 去产生它
• 从其他行/列推球：不会影响这个位置

因此，必要条件是：每个 $1$ 要么上方全是 $1$，要么左方全是 $1$。

三、充分性证明

如果每个 $1$ 都满足上方无 $0$ 或左方无 $0$，则我们可以按 $i+j$ 从大到小（即从右下角向左上角）的顺序，依次将 $1$ 逆向消去：

• 取当前 $i+j$ 最大的 $1$，它一定是某行最右边的 $1$ 或某列最下边的 $1$
• 由于它满足条件，它的上方全是 $1$ 或左方全是 $1$，因此它可以通过一次逆向操作（从左边或上边推入的逆过程）消去
• 消去后，剩余网格仍然满足该性质

因此可以一直消到全 $0$，原状态可达。

四、标程代码（带详细注释）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll t, n, m, a[59][59], vis[59][59];
char s[59];

inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s * w;
}

int main() {
    t = read();
    while (t--) {
        n = read(), m = read();
        
        // 读入网格
        for (ll i = 1; i <= n; i++) {
            scanf("%s", s + 1);
            for (ll j = 1; j <= m; j++) {
                a[i][j] = s[j] - '0';
                vis[i][j] = 0;
            }
        }
        
        // 标记所有能从左边连续推到的位置
        // 即每行从第 1 列开始，连续的一段 1 都能被左边推球产生
        for (ll i = 1; i <= n; i++) {
            for (ll j = 1; j <= m; j++) {
                if (!a[i][j]) break;      // 遇到 0 就停止
                vis[i][j] = 1;            // 标记这个 1 能被左边推球产生
            }
        }
        
        // 标记所有能从上边连续推到的位置
        // 即每列从第 1 行开始，连续的一段 1 都能被上边推球产生
        for (ll j = 1; j <= m; j++) {
            for (ll i = 1; i <= n; i++) {
                if (!a[i][j]) break;      // 遇到 0 就停止
                vis[i][j] = 1;            // 标记这个 1 能被上边推球产生
            }
        }
        
        // 检查是否所有 1 都被标记
        bool fl = 1;
        for (ll i = 1; i <= n && fl; i++) {
            for (ll j = 1; j <= m; j++) {
                if (a[i][j] && !vis[i][j]) {
                    fl = 0;               // 存在一个 1 既不能从左边也不能从上边连续到达
                    break;
                }
            }
        }
        
        puts(fl ? "YES" : "NO");
    }
    return 0;
}

五、算法逻辑总结

六、示例验证

示例 1

001
001
110

• 左边标记：第 1 行：0 开头 → 无标记；第 2 行同理；第 3 行：1,1,0 → 标记 (3,1),(3,2)
• 上边标记：第 1 列：0,0,1 → 标记 (3,1)；第 2 列：0,0,1 → 标记 (3,2)；第 3 列：1,1,0 → 标记 (1,3),(2,3)
• 所有 $1$ 都被标记 → YES

示例 5（最后一个 NO）

000
000
001

• 左边标记：第 3 行：0,0,1 → 第 1 列是 $0$，break → 无法标记 (3,3)
• 上边标记：第 3 列：0,0,1 → 第 1 行是 $0$，break → 无法标记 (3,3)
• (3,3) 未被标记 → NO

七、复杂度分析

• 每个测试用例：$O(n \cdot m)$
• 总 $n \cdot m \le 10000$，$t \le 10000$，完全可行

八、总结

本题的核心转化：

• 正向：每次操作只能把某行/列最前端的 $0$ 变成 $1$
• 逆向：每次只能消去一个上方全 $1$ 或左方全 $1$ 的 $1$
• 结论：所有 $1$ 必须满足“上方无 $0$”或“左方无 $0$”