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 |
dfs怎么过不了#include<iostream> using namespace std; int n,m,ans,sum,MAX; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; char map[122][122]; void dfs(int sx,int sy) { // cout<<sx<<" "<<sy<<" "<<sum<<endl; if(sum<MAX) return; int i; ans++; if(sx<1||sx>n||sy<1||sy>m) return; for(i=0;i<4;i++) { if(sx+dir[i][0]<=n&&sx+dir[i][0]>=1&& sy+dir[i][1]>=1&&sy+dir[i][1]<=m&&map[sx+dir[i][0]][sy+dir[i][1]]=='*') { map[sx+dir[i][0]][sy+dir[i][1]]='.'; dfs(sx+dir[i][0],sy+dir[i][1]); // map[sx+dir[i][0]][sy+dir[i][1]]='*'; } } } int main() { int i,j; while(cin>>m>>n) { if(m==0&&n==0) break; sum=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { cin>>map[i][j]; if(map[i][j]=='*') sum++; } MAX=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(map[i][j]=='*') { ans=0; map[i][j]='.'; dfs(i,j); if(ans>MAX) MAX=ans; sum-=ans; } } cout<<MAX<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator