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

真诚求教,为什么直接BFS错?MS我直接做就AC了

Posted by lqp18_31 at 2009-08-17 12:45:38 on Problem 2312 and last updated at 2009-08-17 12:45:59
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:
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