2013年11月29日 星期五

TIOJ 1198 8-puzzle

[BFS+狀態壓縮]
寫的有點冗:3


#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 10000
#define ALP 1*2*3*4*5*6*7*8*9
#define N(x,y) (((y)-1)*3+(x)-1)
#define SWAP(x,y) x^=y^=x^=y
using namespace std;
int Mts[10]={1,1,2,2*3,2*3*4,
               2*3*4*5,2*3*4*5*6,2*3*4*5*6*7,
               2*3*4*5*6*7*8,2*3*4*5*6*7*8*9};
bool step[ALP+1];
class Status
{
public:
    int I[9];int x,y;int Step;
    Status()
    {
        for(int lx=0;lx<9;lx++)
            I[lx]=9-lx;
        Step=0;
        x=3,y=3;
    }
    int CountPrm()const
    {
        int RE=0;
        for(int lx=0;lx<9;lx++)
        {
            int sum=0;
            for(int ly=lx+1;ly<9;ly++)
                sum+=(I[ly]<I[lx]);
            RE+=sum*Mts[9-lx-1];
        }
        return RE+1;
    }
};
istream& operator>>(istream &in,Status &ss)
{
    for(int lx=0;lx<9;lx++)
        in >> ss.I[lx];
    for(int lx=0;lx<9;lx++)
        if(ss.I[lx]==0)
        {
            ss.y=lx/3+1;
            ss.x=lx%3+1;
            ss.I[lx]=9;
        }
    return in;
}
ostream& operator<<(ostream &out,Status &ss)
{
    for(int lx=0;lx<9;lx++)
    {
        out << ss.I[lx] << " ";
        if(lx%3==2) out << endl;
    }
    out << endl;
    out << "x=" << ss.x << " y=" << ss.y << endl;
    return out;
}
bool operator==(const Status &a1,const Status &b1)
{
    for(int lx=0;lx<9;lx++)
        if(a1.I[lx]!=b1.I[lx]) return false;
    return true;
}
queue<Status> BFS;
int main()
{
    //Initializing
    memset(step,false,sizeof(step));

    Status SStart,SEnd;
    cin >> SStart >> SEnd;
    //cout << SStart;
    BFS.push(SStart);
    if(SStart==SEnd){printf("0\n");return 0;}
    while(BFS.size())
    {
        if(BFS.front()==SEnd) break;
        Status SS=BFS.front();BFS.pop();
        //cout << SS;
        //getchar();
        if(SS.x>=2)
        {
            Status Sa;
            Sa=SS;Sa.Step++;
            SWAP(Sa.I[N(Sa.x-1,Sa.y)],Sa.I[N(Sa.x,Sa.y)]);
            Sa.x--;
            if(step[Sa.CountPrm()]==false)
            {
                step[Sa.CountPrm()]=true;
                BFS.push(Sa);
            }

        }
        if(SS.x<=2)
        {
            Status Sa;
            Sa=SS;Sa.Step++;
            SWAP(Sa.I[N(Sa.x+1,Sa.y)],Sa.I[N(Sa.x,Sa.y)]);
            Sa.x++;
            if(step[Sa.CountPrm()]==false)
            {
                step[Sa.CountPrm()]=true;
                BFS.push(Sa);
            }
        }
        if(SS.y>=2)
        {
            Status Sa;
            Sa=SS;Sa.Step++;
            SWAP(Sa.I[N(Sa.x,Sa.y-1)],Sa.I[N(Sa.x,Sa.y)]);
            Sa.y--;
            if(step[Sa.CountPrm()]==false)
            {
                step[Sa.CountPrm()]=true;
                BFS.push(Sa);
            }
        }
        if(SS.y<=2)
        {
            Status Sa;
            Sa=SS;Sa.Step++;
            SWAP(Sa.I[N(Sa.x,Sa.y+1)],Sa.I[N(Sa.x,Sa.y)]);
            Sa.y++;
            if(step[Sa.CountPrm()]==false)
            {
                step[Sa.CountPrm()]=true;
                BFS.push(Sa);
            }
        }
    }
    printf("%d\n",BFS.front().Step);
    return 0;
}

沒有留言:

張貼留言