题解：UVA1604 立体八数码问题 Cubic Eight-Puzzle

· · 题解

题意

有八个方块，每个上面都染了三种颜色，给定开始和最终状态，求最小步数，30 步之内。

分析

本题为八数码问题的加强版。

考虑利用双向 BFS 实现（为了达到平衡，我取了正向 20 步，反向 10 步）。

我们利用进制思想来存储状态。立方块有 6 种状态，再单独用一个变量记录空白。状态总数为 6^8 \times 9 种。对立方块的状态进行压缩，再额外存储空格。

代码中 dfs 是填充所有可能的 256 种终止状态，而 spread 是对状态的扩展。

实现

复杂度 O(3^{15}) 左右，可以通过。

#include<bits/stdc++.h>
using namespace std;
const int N = 10,M = 1680000,op[] = {3,-3,1,-1};
char g[N][N];
int st[2][M][N];
struct node
{
    int s,p,step;
}sa;
//s: up/front/right 0-6  wrb wbr rwb rbw bwr brw
int f[][4] = {{2,2,5,5},{4,4,3,3},{0,0,4,4},{5,5,1,1},{1,1,2,2},{3,3,0,0}};//s1 udlr flip-> s2
queue<node> q[2];
int p;
void dfs(int x,int y,int s)
{
    if(x == 3)
    {
        q[1].push({s,p,1});
        st[1][s][p] = 1;
        return;
    }
    if(y == 3)
    {
        dfs(x + 1,0,s);
        return;
    }
    if(g[x][y] == 'W') dfs(x,y + 1,s * 6),dfs(x,y + 1,s * 6 + 1);
    else if(g[x][y] == 'R') dfs(x,y + 1,s * 6 + 2),dfs(x,y + 1,s * 6 + 3);
    else if(g[x][y] == 'B') dfs(x,y + 1,s * 6 + 4),dfs(x,y + 1,s * 6 + 5);
    else dfs(x,y + 1,s);
}
node get_s(int a[],int step)
{
    int s = 0,pos = -1;
    for(int i = 0; i < 9; i ++)
        if(~a[i]) s = s * 6 + a[i];
        else pos = i;
    return {s,pos,step};
}
int spread(node x,int o)
{
    int s = x.s;
    int a[N] = {0},t = 8;
    a[x.p] = -1;
    while(s)
    {
        if(t != x.p) a[t] = s % 6,s /= 6;
        t --;
    }
    for(int i = 0; i <= 3; i ++)
    {
        if(x.p >= 6 && !i || x.p <= 2 && i == 1 || x.p % 3 == 2 && i == 2 || x.p % 3 == 0 && i == 3) continue;
        int b = x.p + op[i],c = a[b];
        a[x.p] = f[c][i];
        a[b] = -1;
        node sta = get_s(a,x.step + 1);
        if(st[1 - o][sta.s][sta.p]) return x.step + st[1 - o][sta.s][sta.p] - 1;
        else if(!st[o][sta.s][sta.p]) st[o][sta.s][sta.p] = x.step + 1,q[o].push(sta);
        a[x.p] = -1;
        a[b] = c;
    }
    return -1;
}
int main()
{
    int px,py;
    while(cin>>py>>px,px || py)
    {
        memset(st,0,sizeof st);
        while(!q[0].empty()) q[0].pop();
        while(!q[1].empty()) q[1].pop();
        sa = {0,3 * (px - 1) + py - 1,1};
        q[0].push(sa);
        st[0][0][sa.p] = 1;
        for(int i = 0; i < 3; i ++)
            for(int j = 0; j < 3; j ++)
            {
                cin>>g[i][j];
                if(g[i][j] == 'E') p = 3 * i + j;
            }
        dfs(0,0,0);
        if(st[1][sa.s][sa.p])
        {
            puts("0");
            continue;
        }
        bool flag = 0;
        while(!q[0].empty() && q[0].front().step <= 20)
        {
            int v = spread(q[0].front(),0);
            if(~v)
            {
                flag = 1;
                printf("%d\n",v);
                break;
            }
            q[0].pop();
        }
        if(flag) continue;
        if(q[0].empty())
        {
            puts("-1");
            continue;
        }
        while(!q[1].empty() && q[1].front().step <= 10)
        {
            int v = spread(q[1].front(),1);
            if(~v)
            {
                flag = 1;
                printf("%d\n",v);
                break;
            }
            q[1].pop();
        }
        if(!flag) puts("-1");
    }
    return 0;
}