程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3814 Sawtooth Puzzle 狀態壓縮搜索

ZOJ 3814 Sawtooth Puzzle 狀態壓縮搜索

編輯：C++入門知識

ZOJ 3814 Sawtooth Puzzle 狀態壓縮搜索

由於一個框框只有4種狀態，總狀態數只有4^9，bfs可解。

麻煩的地方就在於模擬。

我的狀態的存法是，將初始狀態看做000000000，若順時針旋轉一次就+1， 3+1=0。

bfs的過程中，需要套一個dfs計算旋轉當前框框會影響到哪些框。

有個地方要注意，就是目標狀態其實不止一種，因為有些框框旋轉之後不變，我們必須把所有可能的目標狀態都計算出來，樣例的中間那個框框就是這種情況。

#include 
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 100005
int h[15];
struct node
{
    int x,dis;
}t,f;
char st[10][10][10];
char ed[10][10][10];
char tst[10][10];
char tzf[10][10];
vector fin[15];
int edge[10][4];
struct fuck
{
    int to,turn;
    fuck(int a,int b){to=a;turn=b;}
    fuck(){}
}v[20];
int top;
bool use[15];
bool FINAL[1111111];
void cal(int now)
{
    memcpy(tst,st[now],sizeof(st[now]));
    for(int d=0;d<4;d++)
    {
        if(memcmp(tst,ed[now],sizeof(tst))==0) {fin[now].push_back(d);}
        for(int i=0;i<8;i++)
        {
            for(int j=0;j<8;j++)
            {
                tzf[j][8-i-1]=tst[i][j];
            }
        }
        memcpy(tst,tzf,sizeof(tzf));
    }
}
bool vis[1111111];
int Turn[9];
bool isok(int x,int y)
{
    return x>=0&&x<3&&y>=0&&y<3;
}
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int op(int a,int b)
{
    if(a-b>=0) return a-b;
    return 3-(b-a-1);
}
bool can(int a,int b,int d)
{
    if(d==0&&edge[a][op(0,Turn[a])]&&edge[b][op(2,Turn[b])]) return true;
    if(d==1&&edge[a][op(1,Turn[a])]&&edge[b][op(3,Turn[b])]) return true;
    if(d==2&&edge[a][op(2,Turn[a])]&&edge[b][op(0,Turn[b])]) return true;
    if(d==3&&edge[a][op(3,Turn[a])]&&edge[b][op(1,Turn[b])]) return true;
    return false;
}
void dfs(int x,int y,int flag)
{
    v[top++]=fuck(x*3+y,flag);
    for(int d=0;d<4;d++)
    {
        int nx=x+dx[d];
        int ny=y+dy[d];
        if(isok(nx,ny)&&use[nx*3+ny]==0&&can(x*3+y,nx*3+ny,d))
        {
            use[nx*3+ny]=true;
            dfs(nx,ny,-flag);
        }
    }
}
void bfs()
{
    memset(Turn,0,sizeof(Turn));
    memset(vis,0,sizeof(vis));
    vis[0]=true;
    queue q;
    f.dis=0;f.x=0;
    q.push(f);
    while(!q.empty())
    {
        f=q.front();q.pop();
        for(int i=0;i<9;i++) Turn[i]=(f.x/h[9-i-1])%4;

        for(int d=0;d<9;d++)
        {
            t=f;
            t.dis++;
            top=0;
            memset(use,0,sizeof(use));
            use[d]=1;
            dfs(d/3,d%3,1);
            int tmp=t.x;
            for(int i=0;i