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 |
真诚求教,为什么直接BFS错?MS我直接做就AC了rt 附上代码 #include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctype.h> #include<algorithm> #include<queue> #include<vector> #include<bitset> #define CL(x) memset( x , 0 , sizeof x ) using namespace std; FILE *fin=freopen( "2312.in" , "r" , stdin ); FILE *fout=freopen( "2312.out" , "w" , stdout ); char map[ 310 ][ 310 ]; int d[ 310 ][ 310 ]; int dx[]={0,0,-1,1},dy[]={-1,1,0,0}; int R,C; const int oo=1000000; void bfs( int sy , int sx ) { queue<int> Q; Q.push( (sy<<10)|sx ); d[ sy ][ sx ]=0; while( !Q.empty() ){ int t=Q.front(); Q.pop(); int my=t>>10 , mx=t^(my<<10) , y , x , dd; for( int i=0 ; i<4 ; i++){ y=my+dy[ i ]; x=mx+dx[ i ]; dd=d[ my ][ mx ]; if( map[ y ][ x ]=='S' || map[ y ][ x ]=='R' ) continue; dd++; if( map[ y ][ x ]=='B' ) dd++; // 如果为blocks 则步数+1 if( dd<d[ y ][ x ] ){ d[ y ][ x ]=dd; Q.push( (y<<10)|x ); } } } } int main() { while( fscanf( fin , "%d%d\n" , &R ,&C) && (R+C) ){ CL( map ); CL( d ); for( int i=1 ; i<=R ; i++){ for( int j=1 ; j<=C ; j++) map[ i ][ j ]=getc( fin ); getc( fin ); } for( int i=0 ; i<=C+1 ; i++) map[ 0 ][ i ]=map[ R+1 ][ i ]='S'; for( int i=0 ; i<=R+1 ; i++) map[ i ][ 0 ]=map[ i ][ C+1 ]='S'; for( int i=1 ; i<=R ; i++) for( int j=1 ; j<=C; j++) if( map[ i ][ j ]=='Y' ){ for( int k=0 ; k<=R+1 ; k++) for( int h=0 ; h<=C+1 ;h++) d[ k ][ h ]=oo; bfs( i , j ); } for( int i=1 ; i<=R ; i++) for( int j=1 ; j<=C; j++) if( map[ i ][ j ]=='T' ){ if( d[ i ][ j ]==oo ) d[ i ][ j ]=-1; fprintf( fout , "%d\n" ,d[ i ][ j ]); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator