题解 P2102 【地砖铺设】

· · 题解

更好体验（大概

看完题第一反应：我明白了（并没有

错误思路：能放颜色的放下去，然后尽量拓展，然后做下一个点,纯模拟

快乐敲完，样例一输，过了

网站一交，WA了

努力想了想

在N<M的时候这种贪心并不正确

例：

错误解法答案： AAABB AAABB AAACA 正解： AAABA AAACB AAABA

所以要改变思路，将原来的“能拓展就拓展”改为“判断下一个点能不能放比当前小的颜色，若不能则继续拓展，反之退出拓展”

来看代码——

//:D
#include<bits/stdc++.h>
using namespace std;
const int dx[4] = {-1, 1, 0, 0}, dy[4]={0, 0, 1, -1};

int n, m;
int a[505][505];

bool dif(int k, int x, int y) {//点(x, y)能否放入颜色k 
    if (x > n || y > m) return 0;//越界 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (a[nx][ny] == k) return 0;//点(x,y)四周有跟颜色k相同的 
    }
    return 1;
}

bool judge(int k, int x, int y) {
    int nx = x, ny = y;//这块瓷砖初始位置在(x,y)，最后右下角会在(x+nx-1,y+ny-1)，看下面代码理解就好了qwq 
    bool f = 0;//是否成功拓展 
    for (int i = 1; i <= n ; i++)
        if (a[nx][y] == -1 && a[x][ny] == -1 &&//没填色..
            dif(k, nx, y)  && dif(k, x, ny)) {//..并且颜色k可以填在(nx,y)与(x,ny)这两个点 
            int s = -1;
            for (int j = 0; j < k; j++)//枚举每一个小于k的颜色 
                if (dif(j, x, ny)) {//如果(x,ny)可以填这个颜色 
                    s = j;//打个标记 
                    break;
                }
            if (s != -1)break;//右边能填更优的颜色，停止拓展 
            f = 1;//上面没break说明已经成功拓展了
            nx++, ny++;//做下一个 
        }
        else break;
    for (int i = x; i < nx; i++)
        for (int j = y; j < ny; j++)
            a[i][j] = k;//全部染成这个颜色 
    return f;
}

int main(){
    memset(a,-1,sizeof(a));//a数组值0表示A，1表示B，以此类推，-1表示还没有颜色
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)//枚举每一个点 
            if (a[i][j] == -1)//如果还妹填色 
                for (int k=0 ; k<=25; k++)//枚举要填的颜色 
                    if (judge(k, i, j)) break;//judge == 1说明填好了，break去做下一个没填色的点 

    //愉快输出—— 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            printf("%c", (char)'A' + a[i][j]);
        printf("\n");
    }
    return 0;
}

后记：

码风垃圾多多包涵

另外，这道题的答案只会用到ABCD四种颜色，大概是四色定理

完结撒花