[Codeforces432E]Square Tiling（贪心+构造）

题目描述

传送门
题意
将一个n*m的矩阵中的每一个方格染色，要求在保证相同颜色连在一起的方格组成一个正方形的前提下字典序最小。字典序逐行逐列比较。

题解

贪心，从上往下从左往右，能小就小。
(i,j)能够染颜色k当且仅当(i-1,j)与(i,j+1)没有染颜色k，且第i行前面的颜色k都是第一行。同时还要判断扩充这个点之后能否形成正方形。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int n,m,nowx,nowy;
int color[105][105];

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
        {
            if (color[i][j]) continue;
            for (int k=1;k<=26;++k)
            {
                if (color[i-1][j]==k||color[i][j+1]==k) continue;
                if (color[i][j-1]==k)
                {
                    if (color[i-1][j-1]==k) continue;
                    nowx=i;
                    while (nowx<n&&color[nowx+1][j-1]==k) nowx++;
                    if (nowx==n) continue;
                    for (int l=i;l<=nowx+1;++l) color[l][j]=k;
                    for (int l=j;l>=j-(nowx-i+1);--l) color[nowx+1][l]=k;
                    break;
                }
                color[i][j]=k;
                break;
            }
        }
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=m;++j)
            putchar(color[i][j]+'A'-1);
        putchar('\n');
    }
}