问题: 引子
时间限制: 1 Sec 内存限制: 256 MB
题面
题面谢绝公开（其实就是懒得放。/滑稽）
题解
真的是发现自己啥也不会了啊QAQ。
这就是一道超级大模拟，然后我就各种懵逼。
首先最先需要考虑的是怎么在一张抽象的图中找水箱。
最令人头疼的是电脑不是人，它是暗箱操作的，根本不能对图有一个全局把握。
于是只能搜索。
图中只有三种东西：水箱，水管，空地。
考虑怎么区分它们。
水箱的组成大致分为三种字符：点、边、数字。
水管的组成只有一种：边。空地只有点。
于是我们可以考虑找到一个数字，以该数字为起点进行bfs，遇边界返回，同时处理出水箱的上下左右界。
另开一个int数组将水箱对应的矩阵全部置成该数字方便查询。
找到水箱后有两个操作：
1.左右两边同步从下往上搜，找到连出水箱的水管。
2.dfs找到水管连接的下一个水箱。
于是分出两个函数分别进行操作，相互调用。就这样模拟灌水就行啦！
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<cmath> #include<algorithm> #define rint register int using namespace std; int n,m,sum_box,map[1003][1003],pos; int lef[100005],rig[100005],upd[100005],dow[100005]; char in_map[1003][1003],ch; bool cy[1003][1003],vis[1003][1003]; struct node{int x,y;}zb[1003*1003]; stack <int> ans_box; inline void dfs(int,int,int,int,int); inline void bfs(int x,int y,int num) { // cout<<x<<' '<<y<<endl; queue <node> q;map[x][y]=num; q.push((node){x,y}); while(!q.empty()) { // cout<<q.size()<<endl; int lx=q.front().x,ly=q.front().y;q.pop(); // cout<<"("<<lx<<","<<ly<<")"<<endl; if(!vis[lx-1][ly]&&in_map[lx-1][ly]!='-') { vis[lx-1][ly]=1,q.push((node){lx-1,ly}),map[lx-1][ly]=num; // cout<<"upd:"<<in_map[lx-1][ly]<<endl; } if(!vis[lx+1][ly]&&in_map[lx+1][ly]!='-') { vis[lx+1][ly]=1,q.push((node){lx+1,ly}),map[lx+1][ly]=num; // cout<<"dow:"<<in_map[lx+1][ly]<<endl; } if(!vis[lx][ly-1]&&in_map[lx][ly-1]!='|') { vis[lx][ly-1]=1,q.push((node){lx,ly-1}),map[lx][ly-1]=num; // cout<<"lef:"<<in_map[lx][ly-1]<<endl; } if(!vis[lx][ly+1]&&in_map[lx][ly+1]!='|') { vis[lx][ly+1]=1,q.push((node){lx,ly+1}),map[lx][ly+1]=num; // cout<<"rig:"<<in_map[lx][ly+1]<<endl; } } return ; } inline void work(int x) { // cout<<x<<endl; for(rint i=dow[x];i>=upd[x];i--) { if(in_map[i][lef[x]-1]=='-') dfs(i,lef[x],i,lef[x]-1,0); if(in_map[i][rig[x]+1]=='-') dfs(i,rig[x],i,rig[x]+1,0); } printf("%d ",x); } inline void dfs(int stx,int sty,int enx,int eny,int fx) { if(in_map[enx][eny]=='-'&&in_map[stx][sty]=='|'&&fx) { work(map[enx+1][eny]);return; } if(in_map[enx][eny]=='-') { if(sty<eny) dfs(enx,eny,enx,eny+1,1); else dfs(enx,eny,enx,eny-1,1); } else if(in_map[enx][eny]=='|')dfs(enx,eny,enx+1,eny,1); else if(in_map[enx][eny]=='+') { if(in_map[stx][sty]=='-')dfs(enx,eny,enx+1,eny,1); else { if(in_map[enx][eny-1]=='-')dfs(enx,eny,enx,eny-1,1); else dfs(enx,eny,enx,eny+1,1); } } } int main() { scanf("%d %d",&n,&m); for(rint i=1;i<=n;++i)scanf("%s",in_map[i]+1); // cout<<"aa"<<endl; for(rint i=1;i<=n;++i) { int j=1; while(j<=m) { int lin=0; while((in_map[i][j]<'0'||in_map[i][j]>'9')&&j<m)j++; while((in_map[i][j]>='0'&&in_map[i][j]<='9')&&j<m) lin=(lin<<3)+(lin<<1)+(in_map[i][j]-'0'),j++; // cout<<lin<<endl; if(lin) { pos=j-1;while(in_map[i][pos]!='|')pos++;rig[lin]=pos; pos=j-1;while(in_map[i][pos]!='|')pos--;lef[lin]=pos; pos=i;while(in_map[pos][j-1]!='-')pos--;upd[lin]=pos; pos=i;while(in_map[pos][j-1]!='-')pos++;dow[lin]=pos; sum_box++,bfs(i,j-1,lin); } j++; } } // cout<<"aa"<<endl; // for(rint i=1;i<=n;++i,cout<<endl) // for(rint j=1;j<=m;++j) // cout<<map[i][j]<<' '; work(1); return 0; }