E. Polygon - 题解

比赛与标签

比赛: Codeforces Round 644 (Div. 3) 标签: dp, graphs, implementation, shortest paths 难度: *1300

题目大意喵~

主人 sama，你好呀！这道题是关于一个叫做 "Polygon" 的军事演习的喵~

想象一下，我们有一个 n x n 的方格棋盘，一开始里面全都是 '0'。然后在棋盘的第一行上面和第一列左边，都排满了大炮。当大炮开火时，会射出一个 '1'。

这个 '1' 会沿着直线前进（从上往下，或者从左往右），直到它撞到棋盘的边界，或者撞到另一个已经存在的 '1'。然后，它就会停在撞上障碍物的前一个格子里。

现在呢，我们拿到了一份演习结束后的棋盘报告（一个 n x n 的 01 矩阵），需要判断这个最终的局面是否可能通过一系列的射击达成。如果可能，就输出 "YES"，否则就输出 "NO" 呐。

简单来说，就是给你一个 01 矩阵，问它是不是一个合法的最终状态，喵~

解题思路呐~

嘿嘿，这个问题看起来可能有点复杂，但只要我们抓住核心，就会变得非常简单哦！让本猫娘带你一步步分析吧！

我们来逆向思考一下：一个 '1' 最终能够停在格子 (i, j)，需要满足什么条件呢？

根据规则，'1' 会一直飞，直到遇到障碍物。那么，要让一个 '1' 停在 (i, j)，它的前进方向上必须紧邻着一个障碍物。

有两种情况可以让 '1' 停在 (i, j)：

从左边射击：位于第 i 行左侧的大炮开火，'1' 向右飞行。为了让它停在 (i, j)，它的右边，也就是 (i, j+1) 这个位置，必须有一个障碍物。这个障碍物要么是棋盘的右边界（即 j 已经是最后一列 n-1），要么是 (i, j+1) 本身已经有了一个 '1'。
从上面射击：位于第 j 列上方的大炮开火，'1' 向下飞行。为了让它停在 (i, j)，它的下边，也就是 (i+1, j) 这个位置，必须有一个障碍物。这个障碍物要么是棋盘的下边界（即 i 已经是最后一行 n-1），要么是 (i+1, j) 本身已经有了一个 '1'。

所以，对于一个合法的棋盘，任何一个位于 (i, j) 的 '1'，都必须满足以下两个条件中的至少一个：

它在最后一列，或者它的右边 (i, j+1) 也是一个 '1'。
它在最后一行，或者它的下边 (i+1, j) 也是一个 '1'。

我们可以把这个叫做“支撑”原则！每一个 '1' 都需要被它右边或下边的边界或其他 '1' 给“支撑”住，否则它就会继续飞走，停不下来啦。

你看，在最后一行或者最后一列的 '1'，它们天然就被棋盘边界给“支撑”住了，所以它们的存在总是合法的。

那么，我们需要检查的，就是那些既不在最后一行，也不在最后一列的 '1'。对于这样一个位于 (i, j) 的 '1'（其中 i < n-1 且 j < n-1），如果它的右边 (i, j+1) 和下边 (i+1, j) 全都是 '0'，那它就失去了所有的“支撑”，是不可能停在这里的！这种情况一旦出现，整个棋盘就是不合法的。

所以我们的策略就非常清晰了喵~：

遍历所有不在边界上的格子，也就是从 (0, 0) 到 (n-2, n-2)。
如果发现某个格子 (i, j) 是 '1'，就检查它的右边 grid[i][j+1] 和下边 grid[i+1][j]。
如果这两个位置都是 '0'，说明这个 '1' 是“悬空”的，不合法！直接判定为 "NO"。
如果遍历完所有格子都没有发现这种情况，那就说明所有 '1' 都有合法的“支撑”，整个棋盘是可能形成的，判定为 "YES"。

这个检查顺序其实无所谓，但从右下角往左上角检查会更符合“先放置支撑物，再放置被支撑物”的直觉呢。代码里就是这么做的哦！

代码实现喵！

cpp

#include <iostream>
#include <vector>
#include <string>

// 处理单个测试用例的函数喵~
void solve() {
    int n;
    std::cin >> n;
    std::vector<std::string> grid(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> grid[i];
    }

    // 一个 '1' 可以被放在 (i, j) 的条件是：
    // 它从左边射来，被 (i, j+1) 的墙挡住；或者从上面射来，被 (i+1, j) 的墙挡住。
    // “墙”指的是棋盘边界或者另一个 '1'。
    // 这意味着，要让 (i, j) 处存在 '1'，必须满足：
    // (j == n-1 OR grid[i][j+1] == '1') OR (i == n-1 OR grid[i+1][j] == '1')。
    //
    // 这个条件是充分且必要的，我们只需要检查它就好了。
    // 在最后一行 (i=n-1) 或最后一列 (j=n-1) 的 '1' 自动满足条件。
    // 所以我们只需要检查那些不在这些边界上的 '1' 就行了。

    bool possible = true;
    // 我们从右下角开始往左上角检查，这样更符合逻辑，但其实任何顺序都可以的说。
    // 只检查到 n-2 行和 n-2 列，因为最后一行和最后一列的 '1' 总是合法的。
    for (int i = n - 2; i >= 0; --i) {
        for (int j = n - 2; j >= 0; --j) {
            // 如果当前格子是 '1'
            if (grid[i][j] == '1') {
                // 这个 '1' 不在边界上。它必须被它下面或右边的 '1' “支撑”住。
                // 如果下面和右边都是 '0'，那它就是悬空的，不可能被放置在这里。
                if (grid[i+1][j] == '0' && grid[i][j+1] == '0') {
                    possible = false; // 标记为不可能
                    break; // 内层循环没必要继续了
                }
            }
        }
        if (!possible) {
            break; // 外层循环也没必要继续了
        }
    }

    if (possible) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // 加上这个可以让输入输出更快哦，是小技巧喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析的说

时间复杂度: O(n²) 的说。对于每个测试用例，我们最多需要遍历一遍 (n-1) x (n-1) 的子矩阵来检查每个 '1' 是否合法。所以对于一个大小为 n 的棋盘，操作是 O(n²)。如果有 t 个测试用例，总时间复杂度就是 O(t * n²)。
空间复杂度: O(n²) 的说。我们需要一个 n x n 的二维数组（或 vector）来存储输入的棋盘状态，所以空间开销是 O(n²)。

知识点与总结喵~

这道题真有趣，看起来像模拟或者动态规划，但核心却是一个简单的逻辑判断题！

核心思想：逆向思维与必要条件分析 我们没有去想如何一步步构造出目标矩阵，而是反过来思考：一个合法的最终状态必须满足什么性质？通过分析 '1' 存在的必要条件，我们找到了一个非常简单的判定法则。
关键观察：局部依赖性 一个格子 (i, j) 的状态只依赖于它的右边 (i, j+1) 和下边 (i+1, j) 的格子。这种局部依赖关系是解题的关键，它告诉我们不需要进行复杂的全局搜索或模拟。
关于标签的思考 虽然题目被标记为 dp 和 graphs，但最终的解法更偏向于 implementation。我们可以把格子之间的依赖关系看作一个有向无环图（DAG），从 (i, j) 指向 (i, j+1) 和 (i+1, j)。这样一来，问题就变成了检查图中断言的合法性。但幸运的是，我们不需要真的建图，一个简单的循环就足够了，喵~

总之，遇到问题时，先别急着写复杂的算法，试着从结果反推条件，说不定就能发现像这样简洁又漂亮的解法哦！主人 sama，你学会了吗？加油加油！喵~

E. Polygon - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路呐~ ​

代码实现喵！ ​

复杂度分析的说 ​

知识点与总结喵~ ​