Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1475Pushing Boxes

Posted by SDRJ10484 at 2012-05-08 14:52:17
using namespace std;        

const char Dir[4]={ 'N','S','W','E' }; 
const char BLOCK='#';
const char BOX='B';
const char SRC='S';
const char TGT='T';
const int MAXN=20;
const int dr[4]={ -1,1,0,0 }; 
const int dc[4]={ 0,0,-1,1 }; 

struct Cord 
{ 
    int r , c;
} ;

struct Node 
{ 
    Cord Cbox , Cman;    
    int pre , dir;
} ;

Node queue[MAXN*MAXN]; 
Cord Q[MAXN*MAXN]; 
Cord src , tgt , box;
Cord path[MAXN*MAXN]; 
int direc[MAXN*MAXN]; 
bool visited[MAXN][MAXN]; 
bool vis[MAXN][MAXN]; 
char map[MAXN][MAXN]; 
int n , m , step;

inline bool legal( int r , int c )
{ 
    return r>=0&&r<n &&c>=0&&c<m;
} 

inline int opp_dir( int d )
{ 
    if( d&1 ) return d-1;
    return d+1;
} 

bool check_path( Cord st , Cord ed , Cord bx )
{ 
    memset( vis,0,sizeof(vis) );
    vis[st.r][st.c]=1;
    int front=0 , rear=0;
    Q[rear].r=st.r , Q[rear].c=st.c;
    rear++;
    if( st.r==ed.r&&st.c==ed.c ){ 
        return true;
    } 
    while( front!=rear ){ 
        Cord cur=Q[front++]; 
        for( int i=0 ; i<4 ; i++ ){ 
            int r=cur.r+dr[i] , c=cur.c+dc[i]; 
            if( r==bx.r&&c==bx.c ) continue;
            if( legal(r,c)&&map[r][c]!=BLOCK&&!vis[r][c] ){ 
                Cord next;
                next.r=r , next.c=c;
                vis[next.r][next.c]=1;
                Q[rear++]=next;
                if( next.r==ed.r&&next.c==ed.c ){ 
                    return true;
                } 
            
            } 
        } 
    } 
    return false;

} 

int bfs_box( void )
{ 
    memset( visited,0,sizeof(visited) );
    visited[box.r][box.c]=1;
    int front=0 , rear=0;
    queue[rear].Cbox.r=box.r , queue[rear].Cbox.c=box.c;
    queue[rear].Cman.r=src.r , queue[rear].Cman.c=src.c;
    queue[rear].dir=-1 , queue[rear].pre=-1;
    rear++;
    if( box.r==tgt.r&&box.c==tgt.c ){ 
        return 0;
    } 
    while( front!=rear ){ 
        Node cur=queue[front++];    
        for( int i=0 ; i<4 ; i++ ){ 
            int r=cur.Cbox.r+dr[i] , c=cur.Cbox.c+dc[i]; 
            int rr=cur.Cbox.r+dr[opp_dir(i)] , cc=cur.Cbox.c+dc[opp_dir(i)]; 
            if( legal(r,c)&&map[r][c]!=BLOCK&&map[rr][cc]!=BLOCK&&!visited[r][c] ){ 
                Node next;
                next.Cbox.r=r , next.Cbox.c=c;
                next.Cman.r=rr , next.Cman.c=cc , next.pre=front-1 , next.dir=i;
                if( !check_path(cur.Cman,next.Cman,cur.Cbox) ) continue;
                next.Cman.r=cur.Cbox.r , next.Cman.c=cur.Cbox.c;
                visited[next.Cbox.r][next.Cbox.c]=1;
                queue[rear++]=next;
                if( next.Cbox.r==tgt.r&&next.Cbox.c==tgt.c ){ 
                    return rear-1;
                } 
            } 
        } 

    } 
    return -1;


} 

void initi_path( int k )
{ 
    if( queue[k].pre!=-1 ){ 
        initi_path( queue[k].pre );
    } 
    path[step]=queue[k].Cbox;
    direc[step]=queue[k].dir;
    step++;

} 


int bfs_man( Cord st , Cord ed , Cord bx )
{ 
    memset( visited,0,sizeof(visited) );
    visited[st.r][st.c]=1;
    int front=0 , rear=0;
    queue[rear].Cman.r=st.r , queue[rear].Cman.c=st.c;
    queue[rear].dir=-1 , queue[rear].pre=-1;
    rear++;
    if( st.r==ed.r&&st.c==ed.c ){ 
        return 0;
    } 
    while( front!=rear ){ 
        Node cur=queue[front++]; 
        for( int i=0 ; i<4 ; i++ ){ 
            int r=cur.Cman.r+dr[i] , c=cur.Cman.c+dc[i]; 
            if( r==bx.r&&c==bx.c ) continue;
            if( legal(r,c)&&map[r][c]!=BLOCK&&!visited[r][c] ){ 
                Node next;
                next.Cman.r=r , next.Cman.c=c , next.dir=i , next.pre=front-1;
                visited[next.Cman.r][next.Cman.c]=1;
                queue[rear++]=next;
                if( next.Cman.r==ed.r&&next.Cman.c==ed.c ){ 
                    return rear-1;
                } 
            } 

        } 

    } 
    return -1;

} 

void print( int k )
{ 
    if( queue[k].pre!=-1 ){ 
        print( queue[k].pre );
    } 
    if( queue[k].dir!=-1 ){ 
        cout<<(char)(Dir[queue[k].dir]+'a'-'A');
    } 
} 

int main( void )
{ 
    int nCase=1;
    while( cin>>n>>m&&n&&m ){ 
    
        for( int i=0 ; i<n ; i++ ){ 
            for( int j=0 ; j<m ; j++ ){ 
                cin>>map[i][j]; 
                if( map[i][j]==BOX ) box.r=i , box.c=j;
                if( map[i][j]==TGT ) tgt.r=i , tgt.c=j;
                if( map[i][j]==SRC ) src.r=i , src.c=j;
                
            } 
        } 
        int k=bfs_box();
        if( k==-1 ){ 
            cout<<"Maze #"<<nCase++<<endl;
            cout<<"Impossible.\n"<<endl;
            continue;
        } 
        step=0;
        initi_path(k);
        Cord st=src , ed;
        cout<<"Maze #"<<nCase++<<endl;
        for( int i=1 ; i<step ; i++ ){ 
            ed.r=path[i-1].r+dr[opp_dir(direc[i])]; 
            ed.c=path[i-1].c+dc[opp_dir(direc[i])]; 
            int kk=bfs_man( st , ed , path[i-1] );
            print(kk) , cout<<Dir[direc[i]]; 
            st=path[i-1]; 
        } 
        cout<<"\n"<<endl;

    } 

    return 0;

}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator