| ||||||||||
| 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 | |||||||||
一直超时……大牛帮忙看下!跪求!!!!!!!!!!!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator