题意分析

我们需要在给定的 $N×NN×N$ 矩阵中找到三个矩形，使得所有 $'*'$ 都被覆盖，且每个矩形的面积不超过$MM$。目标是找到满足条件的最小总成本（三个矩形内元素和的最小值）。

解题思路

1、收集所有$'*'$的位置。 枚举所有可能的三个矩形组合，确保它们覆盖所有 $'*'$且每个矩形的面积不超过 $MM$。 2、计算每个有效组合的总成本，并记录最小值。 3、优化：由于 $N≤30N≤30$，直接暴力枚举所有可能的矩形组合会非常耗时。可以采用以下优化：对于每个 $'*'$，确定可能覆盖它的矩形范围。使用贪心或动态规划来减少枚举次数。

C++实现

cpp

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
};

struct Rectangle {
    int x1, y1, x2, y2; // top-left (x1,y1), bottom-right (x2,y2)
    int cost;
    int area() const { return (x2 - x1 + 1) * (y2 - y1 + 1); }
};

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

    int X;
    cin >> X;
    while (X--) {
        int N, M;
        cin >> N >> M;
        int C;
        cin >> C;
        vector<Point> stars(C);
        for (int i = 0; i < C; ++i) {
            cin >> stars[i].x >> stars[i].y;
            stars[i].x--; // Convert to 0-based index
            stars[i].y--;
        }
        vector<vector<int>> A(N, vector<int>(N));
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                cin >> A[i][j];
            }
        }

        if (C == 0) {
            cout << 0 << '\n';
            continue;
        }

        int min_total = INT_MAX;
        bool possible = false;

        // Generate all possible rectangles that can cover at least one '*'
        vector<Rectangle> rects;
        for (int x1 = 0; x1 < N; ++x1) {
            for (int y1 = 0; y1 < N; ++y1) {
                for (int x2 = x1; x2 < N; ++x2) {
                    for (int y2 = y1; y2 < N; ++y2) {
                        Rectangle rect{x1, y1, x2, y2, 0};
                        if (rect.area() > M) continue;
                        // Calculate cost
                        int cost = 0;
                        for (int i = x1; i <= x2; ++i) {
                            for (int j = y1; j <= y2; ++j) {
                                cost += A[i][j];
                            }
                        }
                        rect.cost = cost;
                        rects.push_back(rect);
                    }
                }
            }
        }

        // Try all combinations of 3 rectangles
        for (size_t i = 0; i < rects.size(); ++i) {
            for (size_t j = i; j < rects.size(); ++j) {
                for (size_t k = j; k < rects.size(); ++k) {
                    const Rectangle& r1 = rects[i];
                    const Rectangle& r2 = rects[j];
                    const Rectangle& r3 = rects[k];
                    // Check if all stars are covered
                    bool all_covered = true;
                    for (const Point& star : stars) {
                        bool covered = false;
                        if (star.x >= r1.x1 && star.x <= r1.x2 && star.y >= r1.y1 && star.y <= r1.y2) covered = true;
                        if (star.x >= r2.x1 && star.x <= r2.x2 && star.y >= r2.y1 && star.y <= r2.y2) covered = true;
                        if (star.x >= r3.x1 && star.x <= r3.x2 && star.y >= r3.y1 && star.y <= r3.y2) covered = true;
                        if (!covered) {
                            all_covered = false;
                            break;
                        }
                    }
                    if (all_covered) {
                        possible = true;
                        int total_cost = r1.cost + r2.cost + r3.cost;
                        if (total_cost < min_total) {
                            min_total = total_cost;
                        }
                    }
                }
            }
        }

        if (possible) {
            cout << min_total << '\n';
        } else {
            cout << "Impossible" << '\n';
        }
    }

    return 0;
}