题目地址

http://uoj.ac/problem/215

考场上的做法

数据这么小，显然要么手玩要么爆搜咯。

爆搜模拟好难写啊！！！

然后就就纯手玩了 3.5h，玩的欲仙欲死才 47 分。

再次乱搞

试试爆搜。

这次出题人良心福利，checker 居然是发源代码，而且代码挺可读的。那就研究一下。

move(x, y, z) 是执行移动命令，print() 是输出地图，check() 是判断是否完成。

改改改！ move 改成返回值为 bool 表示是否移动成功，check() 改成返回里面的变量 cnt 表示连通块个数。只有 a[N][N] 是地图内容，那就弄个 struct 包起来。

check() 的返回值不错，可以当估价，那就写个 A* 吧。实现 hashcode() 表示哈希函数，以及 operator ==、operator < 作为哈希和堆的操作符。哈希表不知道开多少，那就分块分配，每次 new 1024 个。

开跑！绝大多数点在 2min 内都跑了出来。16 一直 RE，把估价函数改成返回 0/1 就出来了。只有 17 跑了巨久，跑了 40min 才出解，用掉了我 5G 内存。

交一发，发现只有 99 分，第 19 个点少了 1 分。然而我的步数是 19，而 AC 提交的步数是 29，不科学啊。 把估价改成 0，就跑出了 18，于是就 AC 啦！

提交记录

http://uoj.ac/submission/84887

修改版 checker

用 clang-format 给代码加了空格，不喜勿喷

把 FILE 里面的数字改掉就可以跑不同的测试点了。

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define SZ(x) ((int)(x).size())
typedef pair<int, int> pii;
const int DX[] = {-1, 1, 0, 0}, DY[] = {0, 0, 1, -1};
const int N = 32;
const int Base = 233;
const int mod = 3333331;
int n, m;
struct State;
struct Record{State *last; int k0, k1, k2;};

int tmp[N][N], sv[N][N];
set<int> S[10];
queue<pii> Q;
int bo;
void get(int &p) 
{
    int x;
    for (x = getchar();
             (x < '0' || x > '9') && x != '|' && x != '-' && x != '.' && x != ' ';
             x = getchar())
        ;
    if (x == '|' || x == '-')
        p = 1;
    else if (x == '.' || x == ' ')
        p = 0;
    else if (x == '0')
        p = -1;
    else
        p = x - '0';
}
struct State
{
    int a[N][N], p, e;
    Record rec;
    void dfs1(int x, int y, int z) 
    {
        if (x < 1 || x > 2 * n - 1 || y < 1 || y > 2 * m - 1) return;
        if (!a[x][y]) return;
        if (a[x][y] == -1) bo = 0;
        tmp[x + DX[z] * 2][y] = a[x][y];
        a[x][y] = 0;
        rep(i, 0, 3) dfs1(x + DX[i], y + DY[i], z);
        if (a[x + DX[z] * 2][y]) Q.push(mp(x + DX[z] * 2, y));
    }
    void dfs2(int x, int y) 
    {
        if (x < 1 || x > 2 * n - 1 || y < 1 || y > 2 * m - 1) return;
        if (!a[x][y]) return;
        if (tmp[x][y]) return;
        tmp[x][y] = 1;
        rep(i, 0, 3) dfs2(x + DX[i], y + DY[i]);
        dfs2(x, y + 2);
    }
    bool move(State *last, int x, int y, int z) 
    {
        rec = (Record) {last, x, y, z}; ++p;
        if (!a[2 * x - 1][2 * y - 1]) return 0;
        bo = 1;
        rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1) tmp[i][j] = 0, sv[i][j] = a[i][j];
        while (Q.size()) Q.pop();
        dfs1(x * 2 - 1, y * 2 - 1, z);
        while (Q.size()) 
        {
            pii k = Q.front();
            Q.pop();
            dfs1(k.X, k.Y, z);
        }
        if (!bo) 
        {
            rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1) a[i][j] = sv[i][j];
            return 0;
        }
        rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1) if (tmp[i][j]) a[i][j] = tmp[i][j];

        while (1) 
        {
            rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1) tmp[i][j] = 0;
            rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1) if (a[i][j] == -1) dfs2(i, j);
            int bo = 0;
            rep(j, 1, 2 * m - 1) rep(i, 1, 2 * n - 1) if (a[i][j] && !tmp[i][j])
                    bo = 1,
                    a[i][j - 1] = a[i][j], a[i][j] = 0;
            if (!bo) break;
        }

        rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1) if ((i & 1) && (j & 1))
                rep(k, 0, 3) if (a[i][j] >= 1 && a[i][j] <= 5 && a[i][j] == a[i + DX[k] * 2][j + DY[k] * 2]) 
                    a[i + DX[k]][j + DY[k]] = 1;
        return 1;
    }
    void print(FILE *x = stdout) 
    {
        fprintf(x, "p = %d e = %d\n", p, estimate());
        rep(i, 1, 2 * m - 1) 
        {
            rep(j, 1, 2 * n - 1) if ((i & 1) && (j & 1)) 
            {
                if (a[j][2 * m - 1 - i + 1] == 0)
                    fprintf(x, ".");
                else if (a[j][2 * m - 1 - i + 1] == -1)
                    fprintf(x, "0");
                else
                    fprintf(x, "%c", a[j][2 * m - 1 - i + 1] + '0');
            }
            else 
            {
                fprintf(x, "%c", a[j][2 * m - 1 - i + 1]
                    ? i & 1 ? '-' : '|'
                    : (i & 1) && (j & 1) ? '.' : ' ');
            }
            fprintf(x, "\n");
        }
    }
    void dfs3(int x, int y, int z) const
    {
        if (x < 1 || x > 2 * n - 1 || y < 1 || y > 2 * m - 1) return;
        if (a[x][y] < 1 || a[x][y] > 5) return;
        if (tmp[x][y]) return;
        tmp[x][y] = 1;
        S[a[x][y]].insert(z);
        rep(i, 0, 3) if (a[x + DX[i] * 2][y + DY[i] * 2] == a[x][y])
                dfs3(x + DX[i] * 2, y + DY[i] * 2, z);
    }
    int check()
    {
        rep(i, 1, 5) S[i].clear();
        int cnt = 0;
        rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1) tmp[i][j] = 0;
        rep(i, 1, 2 * n - 1) rep(
                j, 1, 2 * m - 1) if ((i & 1) && (j & 1) && a[i][j] >= 1 && a[i][j] <= 5)
                dfs3(i, j, ++cnt);
        cnt = 0;
        rep(i, 1, 5) if (SZ(S[i])) cnt += SZ(S[i]) - 1;
        return e = cnt;
    }
    void read_map()
    {
        p = 0;
        scanf("%d%d", &m, &n);
        rep(i, 1, 2 * m - 1) rep(j, 1, 2 * n - 1) get(a[j][2 * m - 1 - i + 1]);
        rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1) if ((i & 1) && (j & 1))
            rep(k, 0, 3) if (a[i][j] >= 1 && a[i][j] <= 5 && a[i][j] == a[i + DX[k] * 2][j + DY[k] * 2]) 
                a[i + DX[k]][j + DY[k]] = 1;
    }
    int estimate() const {return p + e;} 
    //第 16 和第 19 个点会出问题，要把 + e 删掉。
    bool operator == (const State& S) const
    {
        rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1)
            if(a[i][j] != S.a[i][j]) return 0;
        return 1;
    }
    int hashcode() const
    {
        int ans = 0;
        rep(i, 1, 2 * n - 1) rep(j, 1, 2 * m - 1)
            ans = (ans * Base + a[i][j] + 23) % mod;
        return ans;
    }
    void output()
    {
        if(rec.last) 
        {
            rec.last->output();
            printf("%d %d %d\n", rec.k0, rec.k1, rec.k2);
        }
    }
} Init, Tmp;

struct Hash{State S; Hash *next;} *fir[mod];
State* find(const State& S)
{
    int h = S.hashcode();
    for(Hash *k = fir[h]; k; k = k->next)
        if(k->S == S) return 0;
    static Hash *mem, *top;
    if(mem == top) top = (mem = new Hash[1024]) + 1024;
    *--top = (Hash) {S, fir[h]}, fir[h] = top;
    return &top->S;
}

struct Comp
{
    bool operator() (State *a, State *b) const
    {
        return a->estimate() > b->estimate();
    }
};
priority_queue<State*, vector<State*>, Comp> heap;

int main() 
{
    #define FILE "C20"
    freopen(FILE ".in", "r", stdin);
    Init.read_map();
    heap.push(find(Init));
    int counter = 0;
    while(heap.size())
    {
        State *S = heap.top(); heap.pop();
        Tmp = *S;
        printf("new State %d S = %d p = %d e = %d\n", ++counter, S->hashcode(), S->p, S->estimate());
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                for(int k = 0; k != 2; ++k)
                {
                    Tmp = *S;
                    if(!Tmp.move(S, i, j, k)) continue;
                    State *T = find(Tmp);
                    if(!T) continue;
                    if(!T->check())
                    {
                        puts("Found!");
                        T->print();
                        freopen(FILE ".out", "w", stdout);
                        T->output();
                        return 0;
                    }
                    heap.push(T);
                }
    }
    return 0;
}