uva 312 - Crosswords (II)

Crosswords (II)

A crossword can be stored as a matrix  of zeros and ones. Zero represents white squares and one represents black squares. Some squares of the crossword are numbered and assigned to these numbers are the descriptions of the words that should be written either ``across'' or ``down'' into the crossword. A square is numbered if it is a white square and either (a) the square below it is white and there is no white square immediately above, or (b) there is no white square immediately to its left and the square to its right is white. The squares are numbered from left to right, from the top line to the bottom line.
From the matrix a crossword diagram can be drawn. In the diagram each square is represented by a box  characters. Black square and white squares (numbered and not numbered square) are represented as follows (where nnn is the number of the square):

++++++                        ++++++         ++++++
++++++                        +nnn +         +    +
++++++                        +    +         +    +
++++++                        ++++++         ++++++

The remaining characters of the box are spaces. If black squares are given at the edges, they should be removed from the diagram (see the example). Only use spaces as necessary filling characters. Don't use any unnecessary spaces at the end of the line.

Input

The input file consists of several blocks of lines each representing a crossword. Each block starts with the line containing two integers m < 25 and n < 25 separated by one space. In each of the next m lines there are n numbers 0 or 1, separated by one space. The last block will be empty, m = n = 0.

Output

The output file contains the corresponding crossword diagram for each except the last block. After each diagram there is one empty line.

Sample Input

6 7
1 0 0 0 0 1 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 1 0 0 1 1 1
0 0 0 1 0 0 0
1 0 0 0 0 0 1
5 3
1 0 1
0 0 0
1 1 1
0 0 0
1 0 1
0 0

Sample Output

     +++++++++++++++++++++
     +001 +    +002 +003 +
     +    +    +    +    +
++++++++++++++++++++++++++++++++++++
+004 +    ++++++005 +    +006 +007 +
+    +    ++++++    +    +    +    +
++++++++++++++++++++++++++++++++++++
+008 +    +009 +    +    +010 +    +
+    +    +    +    +    +    +    +
+++++++++++++++++++++    +++++++++++
+    ++++++011 +    +
+    ++++++    +    +
++++++++++++++++++++++++++++++++++++
+012 +013 +    ++++++014 +015 +    +
+    +    +    ++++++    +    +    +
++++++++++++++++++++++++++++++++++++
     +016 +    +    +    +    +
     +    +    +    +    +    +
     ++++++++++++++++++++++++++

     ++++++
     +001 +
     +    +
++++++++++++++++
+002 +    +    +
+    +    +    +
++++++++++++++++


++++++++++++++++
+003 +004 +    +
+    +    +    +
++++++++++++++++
     +    +
     +    +
     ++++++

flood-fill, output

#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iostream>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,M,dir[4][2],num[25][25],maz[25][25];
bool notprint[25][25];
void init(){
    dir[0][0]=-1,dir[1][1]=1,dir[2][0]=1,dir[3][1]=-1;
}
bool isValid(int a,int b){return a>=0&&a<N&&b>=0&&b<M;}
bool isSpace(int a,int b){return isValid(a,b)&&maz[a][b]==0;}
bool isWall(int a,int b){return !isValid(a,b)||maz[a][b]==1;}
bool isOk(int r,int c){
    return maz[r][c]==0&&
        (isWall(r-1,c)&&isSpace(r+1,c)||isWall(r,c-1)&&isSpace(r,c+1));
}
string ita(int a){
    string s;
    while(a>0)s+=(a%10+'0'),a/=10;
    while(s.size()<3)s+='0';
    reverse(s.begin(),s.end());
    return s;
}
bool isEdge(int i,int j){return isValid(i,j)&&i==0||j==0||i==N-1||j==M-1;}
void flood(int r,int c){
    notprint[r][c]=1;
    //if(DBG)printf("fld: %d %d\n",r,c);
    int x,y;
    rep(i,4){
        x=r+dir[i][0],y=c+dir[i][1];
        if(isValid(x,y)&&maz[x][y]==1&&!notprint[x][y])flood(x,y);
        //else if(DBG)printf("notprint  %d %d: %d\n",x,y,notprint[x][y]);
    }
}
void print(int num[][25]){rep(i,N){rep(j,M)printf("%d ",num[i][j]);printf("\n");}}
void print(bool num[][25]){rep(i,N){rep(j,M)printf("%d ",num[i][j]);printf("\n");}}
string intersect(string a,string b){
    //if(DBG)printf("inter\n%s\n%s\n",a.c_str(),b.c_str());
    string s;
    rep(i,max(a.size(),b.size()))
        if(i<a.size()&&i<b.size())s+=((a[i]=='+'||b[i]=='+')?'+':' ');
        else if(i<a.size())s+=a[i];
        else s+=b[i];
    //if(DBG)printf("res\n%s\n",s.c_str());
    return s;
}
void revise(vector<string>&res){
    int cur=3;
    for(int cur=3;cur+1<res.size();cur+=4){
        string s1=res[cur],s2=res[cur+1],s3;
        s3=intersect(s1,s2);
        res.erase(res.begin()+cur+1),res.erase(res.begin()+cur);
        res.insert(res.begin()+cur,s3);
        cur--;
    }
}
void ans(){
    int c=1,d;
    int cnum[25];
    memset(num,0,sizeof(num));
    memset(cnum,-1,sizeof(cnum));
    memset(notprint,0,sizeof(notprint));
    rep(i,N)rep(j,M)if(isOk(i,j))num[i][j]=c++;
    if(DBG){printf("num: \n");print(num);}
    rep(i,N)rep(j,M)if(isEdge(i,j)&&maz[i][j]==1&&!notprint[i][j])flood(i,j);
    if(DBG){printf("edge: \n");print(notprint);printf("\n");}
    rep(i,N)rep(j,M)if(maz[i][j]==0)cnum[i]=j;
    vector<string>res;
    string s;
    rep(i,N){
        rep(k,4){
            s="";
            rep(j,M){
                if(!notprint[i][j]){
                    if(k==0)s+="+++++";
                    if(k==1)
                        if(num[i][j])s+="+"+ita(num[i][j])+" ";
                        else if(maz[i][j]==0)s+="+    ";
                        else s+="+++++";
                    if(k==2)if(maz[i][j]==0)s+="+    "; else s+="+++++";
                    if(k==3)s+="+++++";
                }
                else if(j<=cnum[i])                     //empty cell
                    if(s.size()&&(!notprint[i][j-1]))s+="+    ";   //close
                    else s+="     ";
                else break;
            }
            if(s.size())s+="+";                         //last
            if(DBG)printf("s %s\n",s.c_str());
            res.push_back(s);
        }
    }
    revise(res);
    rep(i,res.size())printf("%s\n",res[i].c_str());
    printf("\n");
}
int main(){
    int n,c;
    init();
    while(cin>>N>>M){
        if(N==0&&M==0)break;
        rep(i,N)rep(j,M)scanf("%d",&maz[i][j]);
        ans();
    }
}