题解 P4205 【[NOI2005]智慧珠游戏 】

Sooke · 2019-02-02 21:07:21 · 题解

解题思路

其实也没什么解题思路，暴力模拟搜索直接上就行了。每次填充靠前的空位。

这里有个看起来非常整齐的写法，也有利于调试，其他题解里没看见过这种写法。

设 len 是当前零件的大小，我们用长宽都为 2 \times len - 1 的字符矩阵来储存各种零件。其中最中心的是当前搜到的位置。

例如：

g[0] = "...";
g[1] = ".AA";
g[2] = ".A.";

需要注意的是，因为我们是从第一行，第二行……这样顺次摆下来的，所以矩阵的最中心首先要被占用，其次最中心位置前面的，必须不能用占用，下面两个就不合法：

g[0] = "...";
g[1] = "..A";
g[2] = ".AA";

g[0] = ".A.";
g[1] = "AA.";
g[2] = "...";

应该这么表示：

g[0] = "..";
g[1] = ".A.";
g[2] = "AA.";

硬生生地去描绘所有零件、所有方向的字符矩阵就好。

然后呢，写个函数，有两种模式。第一种：判断给定的字符矩阵表示的零件是否能在给定的位置放，如果能则放并修改解，返回 true，否则返回 false。为了实现回溯，所以有第二种：扔掉之前放的零件。

最后加一个剪枝（当然正式比赛是不能使用的），用 clock 计时，如果要超时了，则无解（很玄学是不是）。

交上去，发现 90 分，WA 了个点，哈？

原来是把有解判成无解了，说明程序还不够高效。

怎么办？随机是击败出题人最大的利器，考虑给每种零件的枚举顺序随机一下（我因为懒就只把 H 和 C 提前了），而不是 ABCDE... 这样死板地枚举，然后就可以过了。

代码实现

超长代码预警！！！（写起来和看起来都好爽的呢）

#include <ctime>
#include <cstdlib>
#include <iostream>

char f[25][25];
bool used[255];
clock_t st;

inline bool modify(int x, int y, int len, std::string g[7], bool mode) {
    bool flag = true;
    if (mode) {
        for (int i = 1 - len; i < len; i++) {
            for (int j = 1 - len; j < len; j++) {
                if (g[i + len - 1][j + len - 1] != '.' && ((x + i <= 0 && y + j <= 0) || f[x + i][y + j] != '.')) { flag = false; }
            }
        }
        if (flag) {
            for (int i = 1 - len; i < len; i++) {
                for (int j = 1 - len; j < len; j++) {
                    if (g[i + len - 1][j + len - 1] != '.') { f[x + i][y + j] = g[i + len - 1][j + len - 1]; }
                }
            }
        }
    } else {
        for (int i = 1 - len; i < len; i++) {
            for (int j = 1 - len; j < len; j++) {
                if (g[i + len - 1][j + len - 1] != '.') { f[x + i][y + j] = '.'; }
            }
        }
    }
    return flag;
}

void dfs() {
    int x = 0, y, len; std::string g[7];
    for (int i = 1; i <= 10; i++) {
        for (int j = 1; j <= i; j++) {
            if (f[i][j] == '.') { x = i; y = j; break; }
        }
        if (x) { break; }
    }
    // 找到最靠前空位的位置。
    if (!x) {
        // 没有空位，说明填满了，输出解。
        for (int i = 1; i <= 10; i++) {
            for (int j = 1; j <= i; j++) { std::cout << f[i][j]; }
            std::cout << std::endl;
        }
        exit(0);
    }
    if (clock() - st >= 950000) {
        std::cout << "No solution" << std::endl;
        exit(0);
    }
    if (!used['H']) {
        used['H'] = true; len = 3;
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..HHH";
        g[3] = "..HH.";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..HH.";
        g[3] = "..HHH";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..HHH";
        g[3] = "...HH";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..HH.";
        g[3] = ".HHH.";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..H..";
        g[3] = "..HH.";
        g[4] = "..HH.";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..H..";
        g[3] = ".HH..";
        g[4] = ".HH..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..HH.";
        g[3] = "..HH.";
        g[4] = "..H..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..HH.";
        g[3] = "..HH.";
        g[4] = "...H.";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['H'] = false;
    }
    if (!used['C']) {
        used['C'] = true; len = 3;
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..CCC";
        g[3] = "..C..";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..CCC";
        g[3] = "....C";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..CC.";
        g[3] = "..C..";
        g[4] = "..C..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..C..";
        g[3] = "..C..";
        g[4] = "..CC.";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..C..";
        g[3] = "..CCC";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..CC.";
        g[3] = "...C.";
        g[4] = "...C.";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..C..";
        g[3] = "..C..";
        g[4] = ".CC..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..C..";
        g[3] = "CCC..";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['C'] = false;
    }
    if (!used['A']) {
        used['A'] = true; len = 2;
        g[0] = "...";
        g[1] = ".AA";
        g[2] = ".A.";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = "...";
        g[1] = ".AA";
        g[2] = "..A";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = "...";
        g[1] = ".A.";
        g[2] = "AA.";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = "...";
        g[1] = ".A.";
        g[2] = ".AA";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['A'] = false;
    }
    if (!used['B']) {
        used['B'] = true; len = 4;
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...BBBB";
        g[4] = ".......";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...B...";
        g[4] = "...B...";
        g[5] = "...B...";
        g[6] = "...B...";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['B'] = false;
    }
    if (!used['D']) {
        used['D'] = true; len = 2;
        g[0] = "...";
        g[1] = ".DD";
        g[2] = ".DD";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['D'] = false;
    }
    if (!used['E']) {
        used['E'] = true; len = 3;
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..E..";
        g[3] = "..E..";
        g[4] = "..EEE";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..EEE";
        g[3] = "..E..";
        g[4] = "..E..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..EEE";
        g[3] = "....E";
        g[4] = "....E";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..E..";
        g[3] = "..E..";
        g[4] = "EEE..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['E'] = false;
    }
    if (!used['F']) {
        used['F'] = true; len = 4;
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...FFFF";
        g[4] = "....F..";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...FFFF";
        g[4] = ".....F.";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...F...";
        g[4] = "..FFFF.";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...F...";
        g[4] = ".FFFF..";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...F...";
        g[4] = "..FF...";
        g[5] = "...F...";
        g[6] = "...F...";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...F...";
        g[4] = "...F...";
        g[5] = "..FF...";
        g[6] = "...F...";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...F...";
        g[4] = "...FF..";
        g[5] = "...F...";
        g[6] = "...F...";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...F...";
        g[4] = "...F...";
        g[5] = "...FF..";
        g[6] = "...F...";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['F'] = false;
    }
    if (!used['G']) {
        used['G'] = true; len = 3;
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..GGG";
        g[3] = "..G.G";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..G.G";
        g[3] = "..GGG";
        g[4] = ".....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..GG.";
        g[3] = "...G.";
        g[4] = "..GG.";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..GG.";
        g[3] = "..G..";
        g[4] = "..GG.";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['G'] = false;
    }
    if (!used['I']) {
        used['I'] = true; len = 4;
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...III.";
        g[4] = ".....II";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...II..";
        g[4] = "....III";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...III.";
        g[4] = "..II...";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...II..";
        g[4] = ".III...";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...I...";
        g[4] = "...I...";
        g[5] = "...II..";
        g[6] = "....I..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...I...";
        g[4] = "...I...";
        g[5] = "..II...";
        g[6] = "..I....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...I...";
        g[4] = "...II..";
        g[5] = "....I..";
        g[6] = "....I..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...I...";
        g[4] = "..II...";
        g[5] = "..I....";
        g[6] = "..I....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['I'] = false;
    }
    if (!used['J']) {
        used['J'] = true; len = 3;
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..J..";
        g[3] = ".JJJ.";
        g[4] = "..J..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['J'] = false;
    }
    if (!used['K']) {
        used['K'] = true; len = 3;
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..K..";
        g[3] = "..KK.";
        g[4] = "...KK";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..KK.";
        g[3] = "...KK";
        g[4] = "....K";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = "..K..";
        g[3] = ".KK..";
        g[4] = "KK...";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".....";
        g[1] = ".....";
        g[2] = ".KK..";
        g[3] = "KK...";
        g[4] = "K....";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['K'] = false;
    }
    if (!used['L']) {
        used['L'] = true; len = 4;
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...LLLL";
        g[4] = "...L...";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...LLLL";
        g[4] = "......L";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...L...";
        g[4] = "...LLLL";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...L...";
        g[4] = "LLLL...";
        g[5] = ".......";
        g[6] = ".......";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...L...";
        g[4] = "...L...";
        g[5] = "...L...";
        g[6] = "..LL...";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...L...";
        g[4] = "...L...";
        g[5] = "...L...";
        g[6] = "...LL..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...LL..";
        g[4] = "...L...";
        g[5] = "...L...";
        g[6] = "...L...";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        g[0] = ".......";
        g[1] = ".......";
        g[2] = ".......";
        g[3] = "...LL..";
        g[4] = "....L..";
        g[5] = "....L..";
        g[6] = "....L..";
        if (modify(x, y, len, g, true)) { dfs(); modify(x, y, len, g, false); }
        used['L'] = false;
    }
}

int main() {
    for (int i = 1; i <= 10; i++) {
        for (int j = 1; j <= i; j++) {
            std::cin >> f[i][j];
            used[f[i][j]] = true;
        }
    }
    st = clock(); dfs();
    return 0;
}