Codeforces 432E Square Tiling(构造+贪心)

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