PKU 3316 Snakes on a Plane
http://poj.org/problem?id=3316
1が枝分かれ無くつながっているものを蛇とする。
このうち、蛇の両端に他の1と隣接することがないように1を付け足すことができないとき、その蛇を最大蛇という。
与えられた盤面に対して、最大蛇の数を答えろというような問題。
若干面倒くさい感じの実装だと自分は感じました。
1時間も経てば自分でも読解が面倒くさいと思うであろうソース。
string in[200]; bool vis[200][200]; main(){ int n,m; while(cin>>n>>m,n){ rep(i,n)cin>>in[i]; memset(vis,0,sizeof(vis)); int ans=0; rep(i,n){ rep(j,m){ if(vis[i][j] || in[i][j]=='0')continue; set<PI>ap; queue<PI>q; set<int>en; q.push(mp(i,j)); while(!q.empty()){ int cx=q.front().F,cy=q.front().S; q.pop(); if(vis[cx][cy])continue; vis[cx][cy]=true; int env=0; rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || n<=nx || ny<0 || m<=ny)continue; if(in[nx][ny]=='1')++env; if(vis[nx][ny] || in[nx][ny]=='0')continue; q.push(mp(nx,ny)); } en.insert(env); if(env<2)ap.insert(mp(cx,cy)); } if(en.count(3) || en.count(4))continue; bool ok=false; FOR(iter,ap){ int cx=iter->F,cy=iter->S; rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || n<=nx || ny<0 || m<=ny || in[nx][ny]=='1')continue; int num1=0; rep(j,4){ int x=nx+dx[j],y=ny+dy[j]; if(x<0 || n<=x || y<0 || m<=y)continue; if(in[x][y]=='1')++num1; } if(num1==1)ok=true; } } ans+=!ok; } } cout<<ans<<endl; } }