题目题解

问题理解

有一个 $n \times n$ 的方阵，初始全为 $0$。
在每行第 $1$ 列左侧有一门大炮（向右射击），在每列第 $1$ 行上方有一门大炮（向下射击）。
每次射击发射一个 $1$，它沿直线飞行，直到撞到边界或另一个 $1$，然后停在之前的单元格。
给定最终矩阵，问是否存在一个射击序列得到该矩阵。

第一步：射击规则分析

• 从第 $i$ 行左侧的大炮射击：$1$ 从 $(i,1)$ 出发向右，遇到第一个 $1$ 或右边界时停止，停在 $(i, j-1)$。
• 从第 $j$ 列上方的大炮射击：$1$ 从 $(1,j)$ 出发向下，遇到第一个 $1$ 或下边界时停止，停在 $(i-1, j)$。

因此，任何 $1$ 必须是由其左侧或上方的 $1$ 阻挡而产生的，否则它会一直飞到边界。

第二步：必要条件

考虑一个 $1$ 在位置 $(i, j)$（$i < n$ 且 $j < n$）。
它不可能由右侧或下方的 $1$ 阻挡，因为飞行方向只有右和下。
所以它必须满足：要么其右侧有 $1$（即 $a[i][j+1] = 1$），要么其下方有 $1$（即 $a[i+1][j] = 1$）。
否则，这个 $1$ 会继续飞行到边界，无法停在 $(i, j)$。

对于最后一行（$i = n$）和最后一列（$j = n$）的 $1$，它们可以靠边界阻挡，因此无需条件。

第三步：充分性

可以证明，上述条件也是充分的。
构造方法：从下到上、从右到左，依次模拟射击过程。
每个 $1$ 要么由右侧或下方的 $1$ 阻挡，要么在边界上，因此可以按逆序还原出射击顺序。

第四步：算法

1. 读入矩阵 $a$。
2. 从 $i = n-2$ 到 $0$，$j = n-2$ 到 $0$ 遍历：
   • 若 $a[i][j] = 1$ 且 $a[i+1][j] = 0$ 且 $a[i][j+1] = 0$，则输出 "NO"。
3. 若遍历结束未发现矛盾，输出 "YES"。

第五步：时间复杂度

• 每个测试用例 $O(n^2)$。
• 总面积 $\le 10^5$，满足要求。

代码实现

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

bool a[50][50];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < n; j++) {
                a[i][j] = (s[j] == '1');
            }
        }
        
        bool ok = true;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                if (a[i][j] && !a[i + 1][j] && !a[i][j + 1]) {
                    ok = false;
                }
            }
        }
        
        cout << (ok ? "YES" : "NO") << "\n";
    }
    
    return 0;
}

验证样例

输入：

5
4
0010
0011
0000
0000
2
10
01
2
00
00
4
0101
1111
0101
0111
4
0100
1110
0101
0111

输出：

YES
NO
YES
YES
NO

与题目输出一致。

总结

本题的关键在于：

1. 理解 $1$ 必须由右侧或下方的 $1$ 阻挡，否则无法停留在非边界位置。
2. 从右下角向左上角检查，确保每个非边界的 $1$ 都有右侧或下方的邻居为 $1$。
3. 该条件既必要又充分。