[dfs][bfs][模拟] Jzoj P5769 引子

Description

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

数字i所在的矩形代表一个编号为i的水箱。
1号水箱为水箱中枢，有水管连出。除了1号水箱外，其他水箱上方会接进来恰好一条水管，也可能有水管连出。
连出的水管会从水箱侧面连出去，同一个水箱连出去的水管会在不同的行与侧面连接。每一条水管直接连接两个水箱，这意味着不会把水管分叉也不会出现水管交叉的情况。这样，从一个水箱流入另外一个水箱时，水管的走向始终保持行号增加或保持不变。
水会源源不断地涌进1号水箱直到各个水箱水满为止。帮助Slavko计算出各个水箱装满的次序。

Input

输入会给你一个n*m的点阵，点阵字符的全集为{+，|，-，.}
水箱：形状是矩形，四角有+符号，左右为|，上下为-，里面包含一个数字代表水箱的编号，如上图。
管道：一条管道恰好连接两个不同的水箱，|表示管道竖直摆放，- 表示管道水平摆放，其中竖直的管道之间会连接起来，水平的管道会连接起来，+连接竖直和水平的管道（+的上下恰好其中一个为.一个为|，+的左右恰好其中一个为 . 一个为-）。
其余位置用. 来填充。
输入的第1行为两个正整数n，m。
接下来n行描述点阵的信息，每行有m个字符。

Output

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

Sample Input

Input 1
12 13
..+--+.......
+-|..|.......
|.|.1|--+....
|.+--+..|....
|......+----+
+---+..|..2.|
....|..+----+
.+--+........
.|...........
+---+........
|.3.|........
+---+........
Input 2
8 10
..........
.......+-+
...+---|1|
...|...+-+
...|......
..+-+.....
..|2|.....
..+-+.....

Sample Output

Output 1
2
3
1
Output 2
2
1

Data Constraint

【数据范围】
70%的数据：1≤n,m≤100。
100%的数据满足：1≤n,m≤1000

题解

大模拟题，考验码力的题目，不多讲

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <queue>
 7 using namespace std;
 8 char a[1010][1010];
 9 struct edge{ int x,y; }up[1000*1000/9];
10 struct node{int u,v,g,to;}e[1000*1000/9];
11 int b[1010][1010],n,m,mx,cnt,head[1000*1000/9],ans[1000*1000/9],num,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
12 bool check(edge u,int i) { return a[u.x+dx[i]][u.y+dy[i]]!='-'&&a[u.x+dx[i]][u.y+dy[i]]!='|'&&!b[u.x+dx[i]][u.y+dy[i]]; }
13 bool pd(edge u,int i) { return (a[u.x+dx[i]][u.y+dy[i]]=='-'||a[u.x+dx[i]][u.y+dy[i]]=='|'||a[u.x+dx[i]][u.y+dy[i]]=='+')&&!b[u.x+dx[i]][u.y+dy[i]]; }
14 void insert(int u,int v,int s) { e[++cnt].u=u; e[cnt].v=v; e[cnt].g=s; e[cnt].to=head[u]; head[u]=cnt; }
15 void dfs(edge u,int h)
16 {
17     for (int i=0;i<=2;i++)
18         if (pd(u,i))
19         {
20             edge y;
21             y.x=u.x+dx[i]; y.y=u.y+dy[i];
22             b[y.x][y.y]=b[u.x][u.y];
23             dfs(y,h);
24             return;
25         }
26         else 
27             if (b[u.x+dx[i]][u.y+dy[i]]!=b[u.x][u.y]&&b[u.x+dx[i]][u.y+dy[i]])
28             {
29                 insert(b[u.x][u.y],b[u.x+dx[i]][u.y+dy[i]],h);
30                 return;
31             }
32 }
33 void bfs()
34 {
35     queue<edge> Q; queue<edge> E;
36     while (!Q.empty()) Q.pop(); while (!E.empty()) E.pop();
37     for (int i=1;i<=mx;i++) 
38         if (up[i].x&&up[i].y) 
39         {
40             Q.push(up[i]);
41             b[up[i].x][up[i].y]=i;
42         }
43     while (!Q.empty()) 
44     {
45         edge u=Q.front();Q.pop();
46         for (int i=0;i<=3;i++) 
47         {
48             if (check(u,i)) 
49             {
50                 edge y;
51                 y.x=u.x+dx[i]; y.y=u.y+dy[i];
52                 Q.push(y);
53             }
54             else 
55             {
56                 edge y;
57                 y.x=u.x+dx[i]; y.y=u.y+dy[i];
58                 E.push(y);
59             }
60             b[u.x+dx[i]][u.y+dy[i]]=b[u.x][u.y];
61         }
62     }
63     while (!E.empty()) 
64     {
65         edge u=E.front();E.pop();
66         dfs(u,u.x);
67     }
68 }
69 bool cmp(node x,node y) { return x.g<y.g; }
70 void dfs1(int u)
71 {
72     for (int i=head[u];i;i=e[i].to) dfs1(e[i].v);
73     ans[++num]=u;
74 }
75 int main()
76 {
77     freopen("clickbait.in","r",stdin);
78     freopen("clickbait.out","w",stdout);
79     scanf("%d%d",&n,&m);
80     for (int i=1;i<=n;i++)
81     {
82         scanf("%s",a[i]+1);
83         int x=0,y=0;
84         for (int j=1;j<=m;j++)
85             if (a[i][j]>='0'&&a[i][j]<='9') x=x*10+a[i][j]-'0',y=j;
86             else up[x].x=i,up[x].y=y,mx=max(mx,x),x=0;
87     }
88     bfs();
89     sort(e+1,e+cnt+1,cmp);
90     memset(head,0,sizeof(head));
91     for (int i=1;i<=cnt;i++) e[i].to=head[e[i].u],head[e[i].u]=i;
92     dfs1(1);
93     for (int i=1;i<=num;i++) printf("%d
",ans[i]);
94     return 0;
95 }