| ||||||||||
| 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