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

DFS居然没过,我汗

Posted by dynamic_study at 2009-08-02 19:14:12 on Problem 3620
#include<iostream>
using namespace std;
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
bool flag[151][151];
struct node
{
	int x,y,num;
}a[100001];
int main()
{
	int n,m,ke,i,j,MAX,h,k,ans,tx,ty,t,cnt,p,q;
	while(cin>>n>>m>>ke)
{
	memset(flag,false,sizeof(flag));
	for(i=0;i<ke;i++)
	{
		cin>>p>>q;
		flag[p-1][q-1]=true;//flag[q-1][p-1]=
	}
        MAX=0;
	for(i=0;i<n;i++)//1
	{
		for(j=0;j<m;j++)//2
		{
			if(flag[i][j]==true)//3
			{
				a[0].x=i;
				a[0].y=j;
				cnt=1;
				a[0].num=cnt;
				flag[i][j]=false;
				h=0;k=1;
				ans=0;
				while(h<k)//4
				{
					if(ans<a[h].num)
						ans=a[h].num;
                    for(t=0;t<4;t++)//5
					{
						tx=a[h].x+d[t][0];
						ty=a[h].y+d[t][1];
						if(tx>=0&&tx<n&&ty>=0&&ty<m&&flag[tx][ty]==true)
						{
							flag[tx][ty]=false;
							a[k].x=tx;
							a[k].y=ty;
							a[k].num=++cnt;
							k++;
						}

					}//5
					h++;
				}//4

			}//3
			if(ans>MAX)
				MAX=ans;
		}//2
	}//1
	cout<<MAX<<endl;
}
	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