网上冲浪时，Slavko被冲到了水箱里，水箱由上而下竖直平面。示意图如下：

 

数字i所在的矩形代表一个编号为i的水箱。

1号水箱为水箱中枢，有水管连出。除了1号水箱外，其他水箱上方会接进来恰好一条水管，也可能有水管连出。

连出的水管会从水箱侧面连出去，同一个水箱连出去的水管会在不同的行与侧面连接。每一条水管直接连接两个水箱，这意味着不会把水管分叉也不会出现水管交叉的情况。这样，从一个水箱流入另外一个水箱时，水管的走向始终保持行号增加或保持不变。

水会源源不断地涌进1号水箱直到各个水箱水满为止。帮助Slavko计算出各个水箱装满的次序。

 

Input

输入会给你一个n*m的点阵，点阵字符的全集为{+，|，-，.}

水箱：形状是矩形，四角有+符号，左右为|，上下为-，里面包含一个数字代表水箱的编号，如上图。

管道：一条管道恰好连接两个不同的水箱，|表示管道竖直摆放，- 表示管道水平摆放，其中竖直的管道之间会连接起来，水平的管道会连接起来，+连接竖直和水平的管道（+的上下恰好其中一个为.一个为|，+的左右恰好其中一个为 . 一个为-）。

其余位置用. 来填充。

输入的第1行为两个正整数n，m。

接下来n行描述点阵的信息，每行有m个字符。

 

Output

输出水箱被浸满的顺序，每行一个序号。

 

 

Sample Input

Input 112 13..+--+.......+-|..|.......|.|.1|--+....|.+--+..|....|......+----++---+..|..2.|....|..+----+.+--+.........|...........+---+........|.3.|........+---+........Input 28 10.................+-+...+---|1|...|...+-+...|........+-+.......|2|.......+-+..... 

Sample Output

Output 1231Output 221 

 

Data Constraint

 

【数据范围】

70%的数据：1≤n,m≤100。

100%的数据满足：1≤n,m≤1000

分析

一道比较简单的模拟，显然深度优先就先，搞个排序再DFS就行了

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N=1002;char c[N][N];struct Point {    int x,y;}st[N*N/9];int b[N][N];int n,m,mx;struct Edge {    int u,v,dep,nx;}g[N*N/9];int cnt,list[N*N/9];int dx[4]={
    0,1,0,-1},dy[4]={
    1,0,-1,0};int ans[N*N/9],acnt;void Add(int u,int v,int dep) {    g[++cnt].u=u;g[cnt].v=v;g[cnt].dep=dep;g[cnt].nx=list[u];list[u]=cnt;}void Init() {    scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++) {        scanf("%s",c[i]+1);        int num=0,k=0;        for (int j=1;j<=m;j++) {            if (c[i][j]>='0'&&c[i][j]<='9') num=num*10+c[i][j]-'0',k=j;            else st[num].x=i,st[num].y=k,mx=max(mx,num),num=0;        }    }}bool Check1(Point u,int i) {    return c[u.x+dx[i]][u.y+dy[i]]!='-'&&c[u.x+dx[i]][u.y+dy[i]]!='|'&&!b[u.x+dx[i]][u.y+dy[i]];}bool Check2(Point u,int i) {    return (c[u.x+dx[i]][u.y+dy[i]]=='-'||c[u.x+dx[i]][u.y+dy[i]]=='|'||c[u.x+dx[i]][u.y+dy[i]]=='+')&&!b[u.x+dx[i]][u.y+dy[i]];}void Dfs(Point u,int dep) {    for (int i=0;i<3;i++) {        if (Check2(u,i)) {            Point y;            y.x=u.x+dx[i];y.y=u.y+dy[i];            b[y.x][y.y]=b[u.x][u.y];            Dfs(y,dep);            return;        }        else if (b[u.x+dx[i]][u.y+dy[i]]!=b[u.x][u.y]&&b[u.x+dx[i]][u.y+dy[i]]) {            Add(b[u.x][u.y],b[u.x+dx[i]][u.y+dy[i]],dep);            return;        }    }}void Bfs() {    queue
           
             q; queue
            
              h; while (!q.empty()) q.pop(); while (!h.empty()) h.pop(); for (int i=1;i<=mx;i++) if (st[i].x&&st[i].y) { q.push(st[i]); b[st[i].x][st[i].y]=i; } while (!q.empty()) { Point u=q.front();q.pop(); for (int i=0;i<4;i++) { if (Check1(u,i)) { Point y; y.x=u.x+dx[i];y.y=u.y+dy[i]; q.push(y); } else { Point y; y.x=u.x+dx[i];y.y=u.y+dy[i]; h.push(y); } b[u.x+dx[i]][u.y+dy[i]]=b[u.x][u.y]; } } while (!h.empty()) { Point u=h.front();h.pop(); Dfs(u,u.x); }}bool Cmp(Edge a,Edge b) { return a.dep