网上冲浪时，Slavko被冲到了水箱里，水箱由上而下竖直平面。示意图如下： 数字i所在的矩形代表一个编号为i的水箱。 1号水箱为水箱中枢，有水管连出。除了1号水箱外，其他水箱上方
分析
一道比较简单的模拟，显然深度优先就先，搞个排序再DFS就行了
#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #include <memory.h> 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<Point> q; queue<Point> 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<b.dep; } void Dfs1(int u) { for (int i=list[u];i;i=g[i].nx) Dfs1(g[i].v); ans[++acnt]=u; } void Solve() { memset(list,0,sizeof list); sort(g+1,g+cnt+1,Cmp); for (int i=1;i<=cnt;i++) { g[i].nx=list[g[i].u];list[g[i].u]=i; } Dfs1(1); } void Print() { for (int i=1;i<=acnt;i++) printf("%d\n",ans[i]); } int main() { freopen("clickbait.in","r",stdin); freopen("clickbait.out","w",stdout); Init(); Bfs(); Solve(); Print(); fclose(stdin);fclose(stdout); }View Code