[POI 2015 R1] 印章 Seal

GitHub跳转原题关系图返回列表

每次取最左上仍未覆盖的黑格，它只能对应印章最左上的凸点，于是贪心删去这一整次盖章。

OJ: luogu

题目 ID: P3585

难度:普及/提高-

标签:贪心模拟思维

日期: 2026-06-19 02:40

目录

  1. 题意
  2. 思路
    1. 关键观察：最左上的黑格没有选择
    2. 贪心删除
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给一张 n × m 的目标图案，其中 x 表示必须被印成黑色，. 表示必须保持白色。

再给一个 a × b 的印章，印章上 x 的位置表示凸起，会真正沾墨。

可以把印章平移后反复盖到纸上，但必须满足：

  1. 不能旋转；
  2. 不能盖出纸外；
  3. 同一个格子不能被印两次。

问能否恰好印出目标图案。

思路

先看最直接的想法：把每个盖章位置都当成一个候选操作，然后回溯搜索能不能把所有黑格恰好覆盖一次：

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

// brute.cpp：小数据暴力解。
// 把“每次盖章”当作一次精确覆盖操作，回溯判断能否刚好覆盖所有黑格。
struct Point {
    int x, y;
};

bool dfs(vector<string> &paper, const vector<Point> &stamp_cells, int n, int m, int a, int b) {
    int sx = -1, sy = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (paper[i][j] == 'x') {
                sx = i;
                sy = j;
                break;
            }
        }
        if (sx != -1) {
            break;
        }
    }

    if (sx == -1) {
        return true;
    }

    for (int id = 0; id < (int)stamp_cells.size(); id++) {
        int top = sx - stamp_cells[id].x;
        int left = sy - stamp_cells[id].y;

        bool ok = true;
        vector<Point> covered;

        for (int k = 0; k < (int)stamp_cells.size(); k++) {
            int nx = top + stamp_cells[k].x;
            int ny = left + stamp_cells[k].y;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || paper[nx][ny] != 'x') {
                ok = false;
                break;
            }
            covered.push_back({nx, ny});
        }

        if (!ok) {
            continue;
        }

        for (int k = 0; k < (int)covered.size(); k++) {
            paper[covered[k].x][covered[k].y] = '.';
        }
        if (dfs(paper, stamp_cells, n, m, a, b)) {
            return true;
        }
        for (int k = 0; k < (int)covered.size(); k++) {
            paper[covered[k].x][covered[k].y] = 'x';
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    while (q--) {
        int n, m, a, b;
        cin >> n >> m >> a >> b;

        vector<string> paper(n), stamp(a);
        for (int i = 0; i < n; i++) {
            cin >> paper[i];
        }
        for (int i = 0; i < a; i++) {
            cin >> stamp[i];
        }

        vector<Point> stamp_cells;
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                if (stamp[i][j] == 'x') {
                    stamp_cells.push_back({i, j});
                }
            }
        }

        bool ok;
        if (stamp_cells.empty()) {
            ok = true;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (paper[i][j] == 'x') {
                        ok = false;
                    }
                }
            }
        } else {
            ok = dfs(paper, stamp_cells, n, m, a, b);
        }

        cout << (ok ? "TAK" : "NIE") << '\n';
    }

    return 0;
}

这个做法只适合很小数据，但它能帮助我们发现一个很强的“强制性”。

关键观察：最左上的黑格没有选择

把印章上所有凸起格子拿出来，找出其中“最左上”的那个凸点，记为锚点。

现在考虑当前图案里最左上、还没有被删掉的黑格 (i, j)。

它在任何合法方案里，都只能对应某次盖章中的这个锚点。原因是：

  • 如果它对应的是印章里的其他凸点，那么那次盖章的锚点一定会落在一个更靠上或更靠左的位置；
  • 由于锚点本身也是凸起，会印出一个更早出现的黑格；
  • 这就和 (i, j) 是当前最左上的黑格矛盾。

所以，当前最左上的黑格一旦确定，这次盖章的位置也就被唯一确定了。

贪心删除

于是我们可以直接贪心：

  1. 扫描整张图，找到当前最左上的黑格；
  2. 把印章锚点对准它；
  3. 检查这次盖章的所有凸起位置：
    • 都必须落在纸内；
    • 都必须正好对应当前还没删掉的黑格；
  4. 如果有任何一个位置不满足，答案就是 NIE；
  5. 否则把这次盖章覆盖到的黑格全部删掉，继续处理。

因为每次删掉的是一整次真实盖章，所以不会重复覆盖；而最左上的黑格又是被强制决定的，所以这个过程不会错过合法方案。

总工作量也很小：印章的每个凸点只会在真正删除某次盖章时被访问一次，总体就是线性级别。

代码

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

struct Point {
    int x, y;
};

int q;

bool solve_one() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;

    vector<string> paper(n);
    vector<string> stamp(a);
    for (int i = 0; i < n; i++) {
        cin >> paper[i];
    }
    for (int i = 0; i < a; i++) {
        cin >> stamp[i];
    }

    vector<Point> cells;
    int anchor_x = -1;
    int anchor_y = -1;

    for (int i = 0; i < a; i++) {
        for (int j = 0; j < b; j++) {
            if (stamp[i][j] == 'x') {
                if (anchor_x == -1) {
                    anchor_x = i;
                    anchor_y = j;
                }
                cells.push_back({i, j});
            }
        }
    }

    int black_cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (paper[i][j] == 'x') {
                black_cnt++;
            }
        }
    }

    if (cells.empty()) {
        return black_cnt == 0;
    }

    vector<Point> offset;
    for (int i = 0; i < (int)cells.size(); i++) {
        offset.push_back({cells[i].x - anchor_x, cells[i].y - anchor_y});
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (paper[i][j] != 'x') {
                continue;
            }

            // 当前最左上的黑格，必须对应印章锚点。
            for (int k = 0; k < (int)offset.size(); k++) {
                int nx = i + offset[k].x;
                int ny = j + offset[k].y;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || paper[nx][ny] != 'x') {
                    return false;
                }
            }

            for (int k = 0; k < (int)offset.size(); k++) {
                int nx = i + offset[k].x;
                int ny = j + offset[k].y;
                paper[nx][ny] = '.';
            }
        }
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> q;
    while (q--) {
        cout << (solve_one() ? "TAK" : "NIE") << '\n';
    }

    return 0;
}

复杂度

  • 时间复杂度：O(nm+ab)O(nm + ab)
  • 空间复杂度：O(ab)O(ab)

总结

这题表面像 exact cover，但因为“不允许重复覆盖”，最左上的黑格其实会强制决定下一次盖章位置。

抓住这个唯一性以后，整题就从回溯搜索变成了顺序贪心删除。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析