厦门大学“网宿杯“17届程序设计竞赛 G-正方形打野

思维

题意：
大司马的重要理论成果之一即所谓正方形打野，本题恰好与正方形相关。
大司马的家的地板可以看成有n×m个格子的矩形。现在他需要用一些颜色的瓷砖来铺满这个房间，每种颜色的瓷砖摆放数量不受限制，但不能在同一个格子上覆盖多块瓷砖，更不能有空格子。
所有的瓷砖都是正方形的，然而这些瓷砖的边长却不一定相等，如:1×1的瓷砖可以覆盖一个格子，2×2的瓷砖可以覆盖4个格子。每一种不同的瓷砖的颜色分别为大写字母A,B,C,D,E等以此类推，本题数据保证所需颜色不会超过26种。
大司马是一个有强迫症的人，他不能忍受地板上出现一个非正方形的色块，即所有同色连通块必须为正方形，这里的连通指上下左右四连通。
当大司马的房子为4×3时那么他的地板可以覆盖成这样:
AAA
AAA
AAA
BCB
不能覆盖成这样:
AAA
AAA
AAA
ACB
因为A对应的同色连通块不是正方形，多了一块角。
大司马希望按照从上到下，从左到右的顺序他房子地板颜色的字典序最小。
即将第一行，第二行……第n行从左到右对应的字母序列串成一个字符串，其字典序最小。
对于给定的n,m，请你输出对应的方案。

分析

这一题，看上去容易，但是其实分析起来情况是比较复杂的。万万不可眼高手低，上来就做。

我们仔细看这道题的要求：
1.保证所有连通块是正方形
2.尽量让这个地板从上到小，从左到右最小
那么我们想想，首相对于第一个格子我们首先肯定会铺A之后向右看尽量铺设A直到这一行铺满
或者说是列数不足以让我们维持正方形了。
这里我们只要贪心的考虑让右边的格子尽量小就可以了，无需考虑下方。
那关键是接下来倘若行数没有铺完列数铺完的情况下怎么考虑？
例：
AAAABA
AAAACB
AAAABA
AAAACB
我们是怎样得出右边的
BA
CB
BA
CB
的呢？
我们在上面的分析中有一句话：
这里我们只要贪心的考虑让右边的格子尽量小就可以了
也就是说我们只用考虑右方。
假设我们现在开始铺设瓷砖B，我们判断下一个即第一行最后一列该铺设什么
我们有两种选择：
1.铺设瓷砖B同时形成正方形(这里要保证不超过列数与行数)
2.铺设其他瓷砖，瓷砖B的正方形到头，新的时***启。(这里的其他瓷砖是可铺设的)
那我们的问题主要是接下来铺设的时刻如何正确选择操作1，2
我们会在两种情况下使用操作2
(1):铺设B无法形成正方形
(2):在可铺设的瓷砖中有比B要小的瓷砖
满足这两个条件的任意一个，我们就不得不选择操作2而非操作1
其实上述的两种情况我们可以归为一种：在可铺设的瓷砖中最小的瓷砖不是B
那么我们就会采取操作2

如此我们从上到下，从左到右的遍历矩阵，正方形的填充矩阵。
代码如下，注意细节：

#include<iostream>;
#include<algorithm>;
#include<vector>;
using namespace std;
int n, m;
char ans[110][110];
int dir[4][2] = { 1,0,-1,0,0,1,0,-1 };

char get(int x0,int y0) {
    vector<char> tmp;
    if (ans[x0][y0])return ans[x0][y0];
    for (int i = 0;i < 4;i++) {
        int x = x0 + dir[i][0];
        int y = y0 + dir[i][1];
        if (x > n || x <= 0 || y > m || y <= 0)continue;
        if (ans[x][y] != 0)tmp.push_back(ans[x][y]);
    }
    for (char ch = 'A';ch <= 'Z';ch++) {
        bool help = true;
        for (char cch : tmp)
            if (cch == ch) {
                help = false;
                break;
            }
        if (help)return ch;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (ans[i][j])continue;
            char mychar = get(i, j);
            int len = 0;
            while (i + len <= n && j + len <= m && get(i, j + len) == mychar)len++;
            for (int k = 0;k < len;k++)
                for (int w = 0;w < len;w++)
                    ans[i + k][j + w] = mychar;
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++)
            cout << ans[i][j];
        cout << endl;
    }
}