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

Output Limit Exceed 半天了,郁闷了,请指教

Posted by 044100324 at 2007-03-17 16:13:59 on Problem 3051
#include "stdio.h"
#include "memory.h"

const int M = 10000;
class queue
{
public:
	int x[M];
	int y[M];
	int head,tail;
	queue(){head=0;tail=0;}
	void inqueue(int tx,int ty)
	{
		x[tail]=tx;
		y[tail]=ty;
		tail++;
	}
	void dequeue(int &tx,int &ty)
	{
		tx=x[head];
		ty=y[head];
		head++;
	}
}q;

char a[90][110];
bool used[90][110];
int rel ,m ;
int w,h;

void solve(int tx, int ty)
{
	int x, y;
	m = 0 ;
	q.head = 0 ;
	q.tail = 0 ;
	q.inqueue( tx, ty);
	m ++ ;
	used[tx][ty] = 1;
	while(1)
	{
		if( q.tail > q.head )
			q.dequeue( x, y);
		else
		{
			rel = rel > m ? rel : m ;
			break;
		}
		if( x >= 0 && x < h && y >=0 && y < w )
		{
			if( x-1 >= 0 && x-1 < h && y >=0 && y< w &&a[x-1][y] == '*'&& used[x-1][y]==0)
			{
				q.inqueue( x - 1, y);
				m ++ ;
				used[x-1][y] = 1;
			}
			if(x+1 >= 0 && x+1 < h && y >=0 && y < w && a[x+1][y] == '*'&& used[x+1][y]==0)
			{
				q.inqueue( x+1, y );
				m ++ ;
				used[x+1][y] = 1;
			}
			if( x >= 0 && x < h && y-1 >=0 && y-1 < w  && a[x][y-1] == '*'&& used[x][y-1]==0)
			{
				q.inqueue( x , y - 1);
				m ++ ;
				used[x][y-1] = 1;
			}
			if( x >= 0 && x < h && y+1 >=0 && y +1< w && a[x][y+1] == '*'&& used[x][y+1]==0)
			{
				q.inqueue( x , y + 1);
				m ++ ;
				used[x][y+1] = 1;
			}
		}

	}
}

int main()
{
	while( scanf( "%d%d", &w,&h) != EOF )
	{
		int i,j;
		for( i = 0 ; i < h ; i ++ )
		{
			scanf( "%s", a[i]);
			memset( used[i] , 0 , 110 * sizeof(bool));
		}
		rel = 0 ;
		for( i = 0 ; i < h ; i ++ )
			for( j = 0 ; j < w ; j ++)
			{
				if( a[i][j] == '*' && used[i][j] == 0 )
					solve(i,j);			
			}
		printf( "%d\n", rel);
	}
	return 0;
}


/*
10 5
..*.....**
.**..*****
.*........
..****.***
..****.***

10 5
..........
..........
..........
..........
..........

10 5
**********
**********
**********
**********
**********

10 5
*.*.*.*.*.
.*.*.*.*.*
*.*.*.*.*.
.*.*.*.*.*
*.*.*.*.*.
*/

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