题解 P5053 【[COCI2017-2018#7] Clickbait】

O2人 · 2019-12-08 16:24:46 · 题解

我发现，我现在在你谷发声（影响力大的）的唯一方式只有发题解了。

这是我初中三年第二次被你谷禁言，在一年的沉寂之后，我又在你谷上发声了，然而好景不长，我又被禁言了。

好了不扯了，看看这题吧。

因为不可能有两个横着的管子插在同一行，所以这题就很好模拟了。

步骤：

1.我们先暴力找到第一个箱子。

2.然后再从下往上枚举水位，一旦发现这一行有管子连着，就马上顺这管子下去,到达箱子x。

3.对x重复2操作

4.如果没管子了，就输出此时编号

所以肯定DFS

Code:

#include <bits/stdc++.h>
using namespace std;
int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
    return ret*f;
}
const int maxn=1005,flg[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,m;
char A[maxn][maxn];
void DFS(int u,int x,int y){
    int L=0,H=0;
    while (A[x][y]!='+') y--;
    while (A[x+L+1][y]!='+') ++L;L+=2;
    while (A[x][y+H+1]!='+') ++H;H+=2;//算箱子宽度和高度
    for (int i=x;i<=x+L-1&&!u;i++)
    for (int j=y;j<=y+H-1&&!u;j++)
    if (A[i][j]>='0'&&A[i][j]<='9'){//找编号
        char ch=A[i][j];
        while (ch>='0'&&ch<='9') u=(u<<3)+(u<<1)+ch-'0',ch=A[i][++j];//类似快读的操作
        break;
    }
    for (int i=x+L-2;i>=x-1;i--)//枚举水位，并遍历
    if (A[i][y-1]=='-'||A[i][y+H]=='-'){
        int nx=i,ny,f;//f是方向，0，1，2，3具体代表什么方向看flg数组
        if (A[i][y-1]=='-') ny=y-1,f=3;
        else ny=y+H,f=1;
        while (true){
            nx+=flg[f][0],ny+=flg[f][1];
            if (A[nx][ny]=='+'){
                if ((f==0||f==2)&&A[nx][ny-1]!='.') f=3;else
                if ((f==0||f==2)&&A[nx][ny+1]!='.') f=1;else
                if ((f==1||f==3)&&A[nx+1][ny]!='.') f=2;//判断管子是否换方向
            }else
            if (A[nx-flg[f][0]][ny-flg[f][1]]=='|'&&A[nx][ny]=='-') break;//判断是否走到水箱上了
        }
        DFS(0,nx,ny);//继续走
    }
    printf("%d\n",u);
}
int main(){
    n=read(),m=read();
    for (int i=1;i<=n;i++) scanf("%s",A[i]+1);
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    if (A[i][j]=='+'){DFS(1,i,j);return 0;}//第一个箱子肯定在最上面，因为'+'上不能插管子
    return 0;
}