题解：P13911 [CSPro 26] 寻宝！大冒险！

alst_1 · 2025-08-31 18:48:16 · 题解

题目传送门

AC代码（我知道你们就是来看这个的）：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
using namespace std;

struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        return static_cast<size_t>(p.first) * 1000000007 + p.second;
    }
};

int main() {
    int n, L, S;
    cin >> n >> L >> S;
    vector<pair<int, int>> points(n);
    unordered_set<pair<int, int>, PairHash> trees;
    for (int i = 0; i < n; i++) {
        cin >> points[i].first >> points[i].second;
        trees.insert(points[i]);
    }

    vector<vector<int>> B(S+1, vector<int>(S+1));
    for (int i = S; i >= 0; i--) {
        for (int j = 0; j <= S; j++) {
            cin >> B[i][j];
        }
    }

    int count = 0;
    for (const auto& p : points) {
        int x = p.first, y = p.second;
        if (x + S > L || y + S > L) {
            continue;
        }
        bool valid = true;
        for (int i = 0; i <= S; i++) {
            for (int j = 0; j <= S; j++) {
                int nx = x + i, ny = y + j;
                bool hasTree = trees.find({nx, ny}) != trees.end();
                if (B[i][j] == 1) {
                    if (!hasTree) {
                        valid = false;
                        break;
                    }
                } else {
                    if (hasTree) {
                        valid = false;
                        break;
                    }
                }
            }
            if (!valid) break;
        }
        if (valid) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

代码步骤：

读取输入：n, L, S 和 n 棵树的坐标，以及藏宝图 B（存储为二维向量，注意输入顺序）。

将树的位置存入集合 trees。

初始化有效候选计数为0。

对于每棵树 (x, y)（即候选位置）：

如果 x + S > L 或 y + S > L，跳过（超出边界）。

遍历藏宝图 B 的每个位置 (i, j)（0 ≤ i, j ≤ S）：

检查点 (x+i, y+j) 是否在树集合中，是否与 B[i][j] 一致。

如果所有位置都匹配，则该候选位置有效。

结束！