| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
1475Pushing Boxesusing 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator