[洛谷P2102] 地砖铺设
在游戏厅大赚了一笔的Randy终于赢到了他想要的家具。乘此机会，他想把自己的房间好好整理一下。在百货公司，可以买到各种各样正方形的地砖，为了美观起见，Randy不希望同样颜色的正方形地砖相邻。所以他找到了Tio来帮忙解决这件事情。Tio很快解决了这个任务。然而，出于某种强迫症，她希望在地上按照长宽划分成网格后，逐行逐列每一块的颜色组成的序列的字典序最小。她希望你帮忙验证一下她的方案。
Input
第一行，包含两个整数N和M，表示房间的长和宽。
Output
N行，每行M列，表示地砖铺设的方案，需要这个方案是字典序最小的合法方案。（可以认为，输出的方案去掉回车后形成的字符串字典序最小）
Example
输入 #1
4 3
输出 #1
AAA
AAA
AAA
BCBScoring
- 对于分值为40的子任务1，保证N,M≤5
- 对于分值为60的子任务2，保证N,M≤100
看完题第一反应：我明白了
思路：能放颜色的放下去，然后尽量拓展，然后做下一个点,纯模拟
//:D
#include<bits/stdc++.h>
using namespace std;
int N, M;
int p[1005][1005];
bool c[3000];
void record(int x, int y){
if (p[x][y] != -1) c[p[x][y]] = 1;//记录四周用过的颜色，第i种颜色用过则c[i]=1
}
int color(int a, int x, int y){
memset(c, 0, sizeof(c));
for (int i = 1; i <= a; i++)//枚举四周一圈的块
{
record(x-1, y+i-1);
record(x+i-1, y-1);
record(x+a, y+i-1);
record(x+i-1, y+a);
}
for (int i = 0; i <= 25; i++)
if (c[i] == 0)//找到第一个四周没有用过的颜色
return i;
}
void work(int n, int m, int x, int y){//未填色的方块大小为N*M，当前在(x,y)(即未填色方块的左上角
//原谅我的垃圾码风
if (n == m){//刚好能拓展完
int s = color(n, x, y);
for (int i = x; i <= x + n; i++)
for (int j = y; j <= y + m; j++)
p[i][j] = s;
return;
}
if (n > m){
int s = color(m, x, y);
for (int i = x; i <= x + m - 1; i++)
for (int j = y; j <= y + m - 1; j++)
p[i][j] = s;
work(n - m, m, x, y + m);
}
if (m > n){
int s = color(n, x, y);
for (int i = x; i <= x + n - 1; i++)
for (int j = y; j <= y + n - 1; j++)
p[i][j] = s;
work(n,m - n, x + n, y);
}
}
int main(){
//freopen("tile.in","r",stdin);
//freopen("tile.out","w",stdout);
memset(p, -1, sizeof(p));
scanf("%d%d", &N, &M);
work(N, M, 1, 1);
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++)
printf("%c", char('A' + p[j][i]));
printf("
");
}
return 0;
}
快乐敲完，样例一输，过了
网站一交，WA了
努力想了想
在N<M的时候这种贪心并不正确
例：
N=3,M=5时
错误解法答案：
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("
");
}
return 0;
}
后记：
算是第一篇题解了，码风垃圾清多多包涵（喂真的有人看吗
另外，这道题的答案只会用到ABCD四种颜色，大概是四色定理
完结撒花