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;
  }
}