洛谷P3969 [TJOI2014]拼图

题目描述

小Z最近迷上了拼图游戏,然而智商有限,他总是无法拼出完整图案。游戏是这样的：首先小Z会得到一些拼图碎片,然后他试着重新排列这些碎片使得它们组成一个大小为4*4的正方形。如下图。注意小Z不能旋转或者翻转这些碎片。

小Z得到如图1的碎片,然后经过重新排列得到图2的正方形。

由于小Z实在太笨了,聪明的你请写一个程序帮助他来解决这个问题吧。

输入输出格式

输入格式：

输入包含多组数据,请使用EOF

每组数据的的第一行包含一个正整数N，表示碎片的个数。接下来输入N个碎片。每个碎片的第一行是两个正整数r和c,表示这个碎片的行数和列数。接下来是r行,每一行包含c个字符'0'或'1'，'1'表示碎片占据这个位置,'0'表示该位置为空。数据保证每个碎片都是完整的一片(即'1'是相互连通的),并且没有行或者列全部为'0'。

输出格式：

如果无法组成一个正方形,输出”No solution”;如果有多组解,输出”Yes, many!”。否则,输出”Yes, only one!”,接下来输出一个4*4的矩阵H,Hij表示位置i,j的碎片编号。碎片编号从1开始。

输入输出样例

输入样例#1：复制

输出样例#1：复制

Yes, only one!
1112
1412
3422
3442
Yes, many!
No solution

说明

数据范围

对于 30% 的数据，N < 5

对于 100% 的数据，N ≤ 16

最近代码能力可能被狗吃了，打了个小清新搜索题。

因为是4*4，并且块不能旋转，因此暴力枚举每一块放哪里带一个剪枝就可以过了。

#include<cstdio>
#include<cstring>
using namespace std;
char tmp[5];
int n, flag;
struct Piece {
    int n, m, shape[5][5];
    void read() {
        scanf("%d%d", &n, &m);
        for(register int i = 0; i < n; ++i) {
            scanf("%s", tmp);
            for(register int j = 0; j < m; ++j)
                shape[i][j] = tmp[j] - '0';
        }
    }
} item[20];
int vis[5][5], last[5][5];
bool illegal(int x, int y, int id) {
    for(register int i = 0; i < item[id].n; ++i) {
        for(register int j = 0; j < item[id].m; ++j)
        	if(item[id].shape[i][j] && vis[x + i][y + j])
        		return true;
    }
    return false;
}
void put(int x, int y, int id, int t) {
    for(register int i = 0; i < item[id].n; ++i) {
        for(register int j = 0; j < item[id].m; ++j)
        	if(item[id].shape[i][j])
                vis[x + i][y + j] = t;
    }
}
void dfs(int step) {
    if(step == n + 1) {
        memcpy(last, vis, sizeof(vis));
        return ++flag, void();
    }
    if(flag >= 2) return;
    for(register int i = 0; i <= 4 - item[step].n; ++i) 
        for(register int j = 0; j <= 4 - item[step].m; ++j) {
        	if(illegal(i, j, step))	continue;
        	if(flag >= 2) return;
        	put(i, j, step, step), dfs(step + 1);
        	put(i, j, step, 0);
    	}
}
int main() {
    while(~scanf("%d", &n)) {
    	flag = 0;
        for(register int i = 1; i <= n; ++i) 
            item[i].read();
        dfs(1);
        if(!flag) printf("No solution\n");
        else 
        if(flag == 1) {
            printf("Yes, only one!\n");
            for(register int i = 0; i < 4; ++i) {
                for(register int j = 0; j < 4; ++j)
                    printf("%d", last[i][j]);
                putchar('\n');
            }
        } else {
            printf("Yes, many!\n");
        }
    }
    return 0;
}

Rockdu's Blog