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