| ||||||||||
| 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 | |||||||||
为什么我会Time Limit Exceeded#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dx[4] = { 0 , -1 , 1 , 0 };
int dy[4] = { -1 , 0 , 0 , 1 };
char ct[4] = { 'w' , 'n' , 's' , 'e' } ;
int Tx , Ty , Bx , By , Sx , Sy ;
int vis[30][30];
struct node{
int xt , yt , xb , yb ;
string w ;
};
node q[1000 * 400 + 200] ;
int n , m , a[40][40] ;
int head , tail ;
namespace MAP{
int vis[22][22] , head , tail ;
struct point{
int x , y , u , fa ;
};
point q[400 + 100] ;
void bfs( int Sx , int Sy , int Bx , int By ){
memset( vis , 0 , sizeof(vis));
vis[Bx][By] = 1 ; q[1] = (point){ Sx , Sy , 0 , 0 };
vis[Sx][Sy] = 1 ;
head = 0 ; tail = 1 ;
while( head < tail ){
point v = q[++head] ;
for( int i = 0 ; i < 4 ; i ++ ){
int xz = v.x + dx[i] , yz = v.y + dy[i] ;
if( a[xz][yz] && !vis[xz][yz] ){
vis[xz][yz] = ++ tail ;
q[tail].x = xz , q[tail].y = yz ;
q[tail].u = i ; q[tail].fa = head ;
}
}
}
}
bool check( int x , int y ){
return vis[x][y] != 0 ;
}
string ask( int x , int y ){
string e , ans = "" ;
for( int i = vis[x][y] ; i != 1 ; i = q[i].fa){
e = ct[q[i].u] ;
e += ans ;
ans = e ;
}
return ans ;
}
}
bool update( node v ){
MAP :: bfs( v.xt , v.yt , v.xb , v.yb ) ;
for( int i = 0 ; i < 4 ; i ++ ){
int xz = v.xb + dx[i] , yz = v.yb + dy[i] ;
int xv = v.xb + dx[3 - i] , yv = v.yb + dy[3 - i] ;
if( a[xz][yz] && a[xv][yv] && !vis[xv][yv] ){
if( ! MAP::check( xz , yz )) continue ;
string e = MAP :: ask( xz , yz ) ;
q[++tail] = ( node ){ v.xb , v.yb , xv , yv , v.w} ;
q[tail].w += e , q[tail].w += char( ct[3 - i] - 'a' + 'A' ) ;
vis[xv][yv] = 1 ;
if( xv == Tx && yv == Ty ) return true ;
}
}
return false ;
}
void init(){
memset( a , 0 , sizeof(a));
for(int i = 1 ; i <= n ; i ++ ){
for( int j = 1 ; j <= m ; j ++ ){
char ch ;
scanf("%c",&ch);
if( ch == '#' ) a[i][j] = 0 ;
else a[i][j] = 1 ;
if( ch == 'B' ) Bx = i , By = j ;
if( ch == 'T' ) Tx = i , Ty = j ;
if( ch == 'S' ) Sx = i , Sy = j ;
}
scanf("\n");
}
}
int main(){
int test = 0 ;
while(1){
test ++ ;
scanf("%d %d\n",&n,&m) ;
if( n == 0 || m == 0 ) break ;
init();
memset( vis , 0 , sizeof(vis));
head = 0 ;
q[tail = 1] = (node){ Sx , Sy , Bx , By , "" }; vis[Bx][By] = 1 ;
int ck = 0 ;
while( head < tail ){
node v = q[++head] ;
if(update(v)){ ck = 1 ; break ;}
}
printf("Maze #%d\n",test);
if(ck){cout << q[tail].w << endl ; }
else puts("Impossible.");
puts("");
}
return 0 ;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator