题解：P6428 [COCI 2008/2009 #1] MRAVOJED

· · 题解

略微优化的暴力可过。

  1. 遍历每个格子作为左上角，只记录能构成的最大全 x 正方形，减少后续计算量。
  2. 从所有正方形中找两个，检查这两个正方形能否覆盖所有 x。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX = 105;
char g[MAX][MAX];
int r, c;

struct Square {
    int x, y, len;
    Square(int x_, int y_, int l_) : x(x_), y(y_), len(l_) {}
};
vector<Square> squares;

bool is_full(int x, int y, int len) {
//从最大可能边长开始往下试，检查这个正方形里是不是全都是 x
    if (x + len - 1 > r || y + len - 1 > c) return false;
    for (int i = x; i < x + len; ++i)
        for (int j = y; j < y + len; ++j)
            if (g[i][j] != 'x') return false;
    return true;
}

bool cover_all(const Square& a, const Square& b) {
//暴力枚举是不是每个 x 点都在 a 或 b 中
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            if (g[i][j] == 'x') {
                bool in_a = (i >= a.x && i <= a.x+a.len-1 &&
                             j >= a.y && j <= a.y+a.len-1);
                bool in_b = (i >= b.x && i <= b.x+b.len-1 &&
                             j >= b.y && j <= b.y+b.len-1);
                if (!in_a && !in_b) return false;
            }
        }
    }
    return true;
}

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

    cin >> r >> c;
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
            cin >> g[i][j];

    int max_len = max(r, c);
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            for (int len = max_len; len >= 1; --len) {
                if (is_full(i, j, len)) {
                    squares.emplace_back(i, j, len);
                    break;
                }
            }
        }
    }

    int sz = squares.size();
    for (int i = 0; i < sz; ++i) {
        for (int j = i; j < sz; ++j) {
            if (cover_all(squares[i], squares[j])) {
                cout << squares[i].x << " " << squares[i].y << " " << squares[i].len << "\n";
                cout << squares[j].x << " " << squares[j].y << " " << squares[j].len << "\n";
                return 0;
            }
        }
    }

    return 0;
}

对于黄题来讲码量也挺长了。