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

一直超时……大牛帮忙看下!跪求!!!!!!!!!!!

Posted by 326775408 at 2011-05-07 18:16:19 on Problem 3051
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char p[80009];
int w,h,j;
int ans=0,Max=-1000;
int no(int t)
{
    int a,b,c,d;
    a=t-1;b=t+w;c=t-w;
	if(t%w!=0&&p[t+1]=='*')return 0;
	if((a)%w!=0&&p[a]=='*')return 0;
	if(b<=j&&p[b]=='*')return 0;
    if(c>0&&p[c]=='*')return 0;
	return 1;
}
void dfs(int t)
{
    int a,b,c,d;
    a=t-1;b=t+w;c=t-w;d=t+1;
	ans++;
	p[t]='.';
	if(t%w!=0&&p[d]=='*')dfs(d);
	if((a)%w!=0&&p[a]=='*')dfs(a);
	if(b<=j&&p[b]=='*')dfs(b);
    if(c>0&&p[c]=='*')dfs(c);
	if(no(t))
	{
		if(Max<ans)
			Max=ans;
	}
	ans--;
	p[t]='*';
	return;
}
int main() {
	//poj3051;
	int i,coun=0;
	char a;
	scanf("%d %d",&w,&h);
	j=w*h;
	int t;
	getchar();
	for(i=1;i<=j;i++)
	{
		if(i%w!=0)
		scanf("%c ",&p[i]);
		else{
			scanf("%c",&p[i]);
			getchar();
		}
		if(p[i]=='.')coun++;
	}
	for(i=1;i<=j;i++)
	{
		if(p[i]=='*')
		{
			ans=0;
			dfs(i);
		}
		if(Max==w*h-coun)break;
	}
	printf("%d\n",Max);
	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