PKU 1374 Crosswords

http://poj.org/problem?id=1374
与えられた情報からクロスワードのマスの形を出せというような問題。

微妙に実装重視なところとPEラッシュが辛い問題。
クロスワードの上下で完全に空白のところがあったら、その行を取るのかとか考えてたりして結構PE食らいました。
正解者数があまり多く無いですが、やれば解ける問題に入るんじゃないでしょうかね。
あきらかにTLEするアルゴリズムしか思いつけない問題よりはいいと思うんですが、敬遠されているみたいですね。

char out[200][200];

int in[100][100];
int n,m;
bool vis[100][100];

void bfs(int x,int y){
  queue<PI>q;
  q.push(mp(x,y));
  while(!q.empty()){
    int cx=q.front().F,cy=q.front().S;
    q.pop();
    if(vis[cx][cy])continue;
    vis[cx][cy]=true;
    in[cx][cy]=2;
    rep(i,4){
      int nx=cx+dx[i],ny=cy+dy[i];
      if(nx<0 || n<=nx ||
         ny<0 || m<=ny ||
         vis[nx][ny] || in[nx][ny]!=1)continue;
      q.push(mp(nx,ny));
    }
  }
}

void ed(int x,int y){
  rep(i,6)out[x*3][y*5+i]=out[x*3+3][y*5+i]='+';
  rep(i,4)out[x*3+i][y*5]=out[x*3+i][y*5+5]='+';
}

main(){
  bool nf=false;
  while(cin>>n>>m,n|m){
    if(nf)printf("\n\n");
    nf=true;
    rep(i,n)rep(j,m)cin>>in[i][j];
    memset(vis,0,sizeof(vis));
    memset(out,' ',sizeof(out));
    
    rep(i,n){
      if(in[i][0]==1)bfs(i,0);
      if(in[i][m-1]==1)bfs(i,m-1);
    }
    rep(i,m){
      if(in[0][i]==1)bfs(0,i);
      if(in[n-1][i]==1)bfs(n-1,i);
    }

    int num=0;
    int bot=0;
    rep(i,n){
      rep(j,m){
        switch(in[i][j]){
        case 0:
          ed(i,j);
          if(((i==0 || in[i-1][j]!=0) && i+1<n && in[i+1][j]==0) ||
             ((j==0 || in[i][j-1]!=0) && j+1<m && in[i][j+1]==0)){
            ++num;
            out[3*i+1][5*j+1]=num/100+'0';
            out[3*i+1][5*j+2]=num/10%10+'0';
            out[3*i+1][5*j+3]=num%10+'0';
          }
          bot=i+1;
          break;
        case 1:
          ed(i,j);
          rep(x,2)rep(y,4)out[3*i+x+1][5*j+y+1]='+';
          bot=i+1;
          break;
        }
      }
    }
    int to=0;
    bool ps=true;
    bot=n;
    rep(i,bot){
      rep(j,3+(i+1==bot)){
        int e;
        for(e=150;e>=0;--e)
          if(out[to][e]!=' '){
            ps=true;
            break;
          }
        ++e;
        out[to][e]=0;
        if(ps)puts(out[to]);
        ++to;
      }
    }
  }
}