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

Re:我用DFS过了,又写了一个BFS,可是却样例AC,提交WA了,程序条理还算清晰.能否有同学帮我看看?

Posted by pengshihui at 2010-08-01 09:51:16 on Problem 1979
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:
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