push box(bfs).cpp

杭电acm解题报告2001---2099.

#include<cstdio>
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

int n,m;
char game_map[9][9];
bool game_hash[8][8][8][8][8][8][8][8];

struct POINT
{
    int x,y;
    bool operator < (const POINT & a) const
    {
        if(x != a.x)
            return x < a.x;
        else
            return y < a.y;
    }
    bool operator == (const POINT & a) const
    {
        if(x == a.x && y == a.y)
            return true;
        return false;
    }
}t[3];

struct INF
{
    POINT s,b[3];
    int move;
    
    inline bool isend()
    {
        for(int i=0;i<3;i++)
        {
            if(!(b[i] == t[i]))
                return false;
        }
        return true;
    }
    inline bool isok()
    {
        sort(b,b+3);
        if(s.x<0 || s.y<0 || s.x>=n || s.y>=m)
            return false;
        for(int i=0;i<3;i++)
        {
            for(int j=i+1;j<3;j++)
                if(b[i] == b[j])
                    return false;
                if(b[i].x<0 || b[i].y<0 || b[i].x>=n || b[i].y>=m || game_map[ b[i].x ][ b[i].y ] != '.')
                    return false;
        }
        if(game_map[s.x][s.y]!='.' || game_hash[ b[0].x ][ b[0].y ][ b[1].x ][ b[1].y ][ b[2].x ][ b[2].y ][ s.x ][ s.y ])
            return false;
        return true;
    }
    inline void maketag()
    {
        game_hash[ b[0].x ][ b[0].y ][ b[1].x ][ b[1].y ][ b[2].x ][ b[2].y ][ s.x ][ s.y ] = true;
    }
    inline void turn(int d)
    {
        move ++;
        switch(d)
        {
        case 1:
            s.x--;
            break;
        case 2:
            s.y++;
            break;
        case 3:
            s.x++;
            break;
        case 4:
            s.y--;
            break;
        }
        for(int i=0;i<3;i++)
            if(s == b[i])
            {
                switch(d)
                {
                case 1:
                    b[i].x--;
                    break;
                case 2:
                    b[i].y++;
                    break;
                case 3:
                    b[i].x++;
                    break;
                case 4:
                    b[i].y--;
                    break;
                }
                break;
            }
    }
}ans;
queue<INF> SQ;

void bfs()
{
    INF now,next;
    
    while(!SQ.empty())
    {
        now=SQ.front();
        SQ.pop();
        
        if(now.isend())
        {
            ans = now;
            return ;
        }
        for(int i=1;i<=4;i++)
        {
            next = now;
            next.turn(i);
            if(next.isok())
            {
                next.maketag();
                SQ.push(next);
            }
        }
    }
}

int main()
{
    int i,j;
    int bs,ts;
    INF start;
    while(scanf("%d %d",&n,&m)==2)
    {
        bs = ts = 0;
        //printf("Maze #%d\n",ct++);
        getchar();
        for(i=0;i<n;i++)
            gets(game_map[i]);
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
            {
                if(game_map[i][j]=='X')
                {
                    start.s.x = i;
                    start.s.y = j;
                    game_map[i][j] = '.';
                }
                else if(game_map[i][j]=='*')
                {
                    start.b[bs].x = i;
                    start.b[bs++].y = j;
                    game_map[i][j] = '.';
                }
                else if(game_map[i][j]=='@')
                {
                    t[ts].x = i;
                    t[ts++].y = j;
                    game_map[i][j] = '.';
                }
            }
            
            //
            memset(game_hash,0,sizeof(game_hash));
            sort(start.b,start.b+3);
            sort(t,t+3);
            start.maketag();
            start.move =0;
            ans.move = -1;
            while(!SQ.empty())    SQ.pop();
            start.maketag();
            SQ.push(start);
            bfs();
            cout<<ans.move<<endl;
    }
}