构造+贪心，CF 432E，Square Tiling

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 432E - Codeforces

---

二、解题报告

1、思路分析

很简单的一个构造题

考虑字典序从左到右从上到下，所以我们正常遍历

对于当前格子如果空闲，那么找到一个能填的最小字符

然后检查该格子可扩展的最大边长为多少

然后将正方形填字符即可

2、复杂度

时间复杂度： O((MN)^2)空间复杂度：O(MN)

3、代码详解

 ​

#include <bits/stdc++.h>using i64 = long long;void solve() {int n, m;std::cin >> n >> m;std::vector<std::vector<int>> g(n, std::vector<int>(m));std::array<int, 5> dir { 1, 0, -1, 0, 1 };auto check = [&](int i, int j) -> int {if (g[i][j]) return g[i][j];for (int c = 1; c <= 26; ++ c) {bool f = true;for (int k = 0; k < 4; ++ k) {int ii = i + dir[k], jj = j + dir[k + 1];if (ii < 0 || ii >= n || jj < 0 || jj >= m) continue;if (g[ii][jj] == c) f = false;}if (f) return c;}return 0;};for (int i = 0; i < n; ++ i) {for (int j = 0; j < m; ++ j) {if (g[i][j]) continue;int c = check(i, j);int sz = 0;while (j + sz < m && i + sz < n && check(i, j + sz) == c) ++ sz;-- sz;for (int ii = i; ii <= i + sz; ++ ii)for (int jj = j; jj <= j + sz; ++ jj)g[ii][jj] = c;}}for (int i = 0; i < n; ++ i, std::cout << '\n') for (int j = 0; j < m; ++ j)std::cout << char(g[i][j] - 1 + 'A');
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}