Description
下图是一个由容器和管道组成的排水系统。对于这个系统，\(Slavko\) 想知道如果一直向容器1灌水，那么所有容器从空到充满水的顺序。
系统共有 \(K\) 个容器标号为1到 \(K\) 。整个系统可以用 \(N\) 行 \(M\) 列的字符矩阵描述。所有容器都是矩形的，容器和管道的边界用下列字符表示：
‘-’：表示边界的水平部分
‘|’：表示边界的垂直部分
‘+’：表示边界的顶点，即水平与垂直部分的交界点。特别的，容器与管道的交接点使用容器边界的表示字符。
每个容器内部，存在某个位置开始的一串数字表示容器编号，而其它位置都由‘.’表示。例如，标号12的容器内部会出现”12”。
对于除了容器1以外的所有容器，有且仅有一个供水管道从容器上方边界进入。容器1没有供水管道。
每个容器可以有0到多个排水管道从侧面边界连出。同一容器的多个排水管道一定具有不同的高度（即从矩阵不同的行连出）。
每个管道直接连接两个容器，多个管道之间不会相交。每条管道中的水从源容器径直流向目标容器，且管道路线只会向同一行或者下一行延伸。亦即，管道下降后不会再回到之前经过的行。
进入的水在容器中不断积累直到充满容器。在此过程中，如果水面到达容器某个排水管道的高度，接下来的水会从管道流出直到管道填满。
请你帮助 \(Slavko\) 找出容器被灌满的顺序。
注：测试数据保证每个‘+’的上下左右都是一个‘|’、一个‘-’和两个‘.’组成，而且管道只与进入和排出的容器相邻，进入时连接字符为‘|’，排出时连接字符为‘-’。
第一行为两个整数 \(N\)、\(M\)。
接下来 \(N\) 行，每行 \(M\) 个字符，为表示系统的矩阵。
Output
请你输出 \(K\) 行，第 \(i\) 行为第 \(i\) 个被水填满的容器编号。数据保证顺序唯一。
12 13 ..+--+....... +-|..|....... |.|.1|--+.... |.+--+..|.... |......+----+ +---+..|..2.| ....|..+----+ .+--+........ .|........... +---+........ |.3.|........ +---+........
Sample Output
2 3 1
HINT
样例解释：从容器1开始灌水。水面到达高度1时，开始从管道流向容器2。容器2灌满以后，容器1的水面开始继续上升，直到到达高度2，此时开始从管道流向容器3。容器3灌满以后，容器1的水面继续上升直到灌满容器。
【数据规模与约定】
对于 \(70%\) 的数据，\(1 \leq N, M \leq 100\)。
对于 \(100%\) 的数据，\(1 \leq N, M \leq 1000\)。
来源：\(NOI2019\) 北京队集训
想法
第一眼看题没懂，感觉好怕怕 后来再看，就是个大模拟。写完还挺有成就感【捂脸】
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
int n,m;
char mp[N][N];
int be[N][N];
struct con{
int l,r,u,d;
}d[N*N];
int k;
void get_con(int x,int y,int id){
int i=x,j=y;
while(mp[i][j]!='|') j--; d[id].l=j;
j=y;
while(mp[i][j]!='|') j++; d[id].r=j;
j=y;
while(mp[i][j]!='-') i--; d[id].u=i;
i=x;
while(mp[i][j]!='-') i++; d[id].d=i;
for(j=d[id].l;j<=d[id].r;j++) be[d[id].u][j]=id;
}
int find(int x,int y,int dir){
while(!be[x][y]){
if(mp[x][y]=='-'){
if(dir==3) y--;
else y++;
}
else if(mp[x][y]=='|') {
if(dir==0) x--;
else x++;
}
else{
if(dir==3 || dir==1){
if(x>0 && mp[x-1][y]=='|') x--,dir=0;
else x++,dir=2;
}
else{
if(y>0 && mp[x][y-1]=='-') y--,dir=3;
else y++,dir=1;
}
}
}
return be[x][y];
}
void dfs(int u){
int v;
for(int i=d[u].d;i>=d[u].u;i--){
v=0;
if(d[u].l>0 && mp[i][d[u].l-1]=='-') v=find(i,d[u].l-1,3);
if(d[u].r<m-1 && mp[i][d[u].r+1]=='-') v=find(i,d[u].r+1,1);
if(v) dfs(v);
}
printf("%d\n",u);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",mp[i]);
//find con
int x;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(!isdigit(mp[i][j])) continue;
x=mp[i][j] -'0';
while(j+1<m && isdigit(mp[i][j+1])) x=x*10+mp[i][++j]-'0';
k=max(k,x);
get_con(i,j,x);
}
dfs(1);
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/11144266.html
