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

为什么我会Time Limit Exceeded

Posted by weekend1997 at 2013-11-07 19:57:58 on Problem 1475
#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:
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