| ||||||||||
| 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 | |||||||||
Re:我用DFS过了,又写了一个BFS,可是却样例AC,提交WA了,程序条理还算清晰.能否有同学帮我看看?In Reply To:我用DFS过了,又写了一个BFS,可是却样例AC,提交WA了,程序条理还算清晰.能否有同学帮我看看? Posted by:blackerJT at 2009-10-25 09:06:20 > 这里是代码
>
> #include< stdio.h >
> #include< stdlib.h >
> #include< string.h >
>
>
> bool grid[25][25];
> int sum;
> int path[4][2] = { { -1,0 }, { 0,1 }, { 1,0 }, { 0,-1 } };
>
> typedef struct
> {
> int x,y;
> }TEXT;
>
> typedef struct
> {
> TEXT text[2000];
> int front,rear;
> }Queue;
>
> Queue Q;
>
> void Init ( void )
> {
> for( int i = 0; i < 2000; i++ )
> Q.text[i].x = Q.text[i].y = 0;
> Q.front = 0;
> Q.rear = -1;
> }
>
> void EnQueue ( int i, int j )
> {
> Q.rear += 1;
> Q.text[Q.rear].x = i;
> Q.text[Q.rear].y = j;
> }
>
> void DeQueue ( void )
> {
> Q.front += 1;
> }
>
> bool isempty ( void )
> {
> return Q.front > Q.rear ? 1:0;
> }
>
> void BFS( int i, int j )
> {
> int a,b;
> int x,y;
> EnQueue( i,j );
> sum++;
> grid[i][j] = 0;
> while( isempty() == 0 )
> {
> a = Q.text[Q.front].x; //得到队顶元素坐标
> b = Q.text[Q.front].y;
> DeQueue();
> for( int i = 0; i < 4; i++ )
> {
> x = a + path[i][0];
> y = b + path[i][1];
> if( grid[x][y] == 1 )
> { EnQueue( x,y ); sum++; grid[x][y] = 0; }
> }
> }
> }
>
>
>
> int main ( void )
> {
> //freopen( "in.txt", "r", stdin );
> //freopen( "out.txt", "w", stdout );
> int w,h;
> int x,y;
> char c;
> while( scanf("%d %d\n",&w,&h) && w != 0 && h != 0 )
> {
> memset( grid,0,sizeof(grid) );
> for( int i = 1; i <= h; i++ )
> {
> for( int j = 1; j <= w; j++ )
> {
> c = getchar();
> if( c == '.' )
> grid[i][j] = 1;
> else
> if( c == '@' )
> grid[i][j] = 1, x = i, y = j;
> }
> getchar();
> }
> sum = 0;
> BFS( x,y );
> printf("%d\n",sum);
> }
> return 0;
> }
要判断x 和y 是否超出了地图。。。。。。
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator