题目连接：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;
}