大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
题目连接：Codeforces 432E Square Tiling
题目大意：给出一个n∗m的矩阵，要求对该矩阵进行上色，用大写字母。可是每次上色的区域必须是正方形。不求相邻的上色区域不能有同样的颜色，求字典序最小的方案（字典序比較，从左至右，从上到下）
解题思路：用贪心的思想去构造矩阵。由于字典序的优先级为左至右，以及上到下，所以我们每次对于一个未上色点x。y，考虑最少要放到的长度p就可以。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n, m, g[N][N];
void draw(int x, int y, int k, int sign) {
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++)
g[x+i][y+j] = sign;
}
}
int get(int x, int y) {
int v[15];
memset(v, 0, sizeof(v));
for (int i = 0; i < 4; i++) {
int p = x + dir[i][0];
int q = y + dir[i][1];
v[g[p][q]] = 1;
}
for (int i = 1; i <= 10; i++)
if (v[i] == 0)
return i;
return 0;
}
void solve (int x, int y) {
if (y > m) {
y = 1;
x++;
}
if (x > n)
return ;
if (g[x][y]) {
solve(x, y+1);
return;
}
int sign = get(x, y);
int p = 1;
while (true) {
if (p + x > n || p + y > m)
break;
if (g[x][y+p])
break;
int tmp = get(x, y+p);
if (tmp != sign)
break;
p++;
}
draw(x, y, p, sign);
solve(x, y + p);
}
int main () {
scanf("%d%d", &n, &m);
memset(g, 0, sizeof(g));
solve (1, 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
printf("%c", 'A'+g[i][j]-1);
printf("\n");
}
return 0;
}版权声明：本文博客原创文章。博客，未经同意，不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117480.html原文链接：https://javaforall.net
