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