P7185 题解

IsaacX · 2023-11-11 14:29:24 · 题解

P7185

模拟赛出的模拟题。

没什么特别的，直接沿着管道走，走到空缺的就计算答案。

可以用 0,1,2,3 代表四个方向，记录每一种管道的那些方向是开口的，方便判断两个管道是否连通。

dfs 传两个参数，一个是当前位置，一个是走过上一步来的方向，如果遇见十字管道顺着原来的方向走即可。

#include <bits/stdc++.h>
using namespace std;
int n,m,mp[30][30];
int fx[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int bk[10][4];
struct Node
{
    int x,y;
}st,ed;
int R(int x)//求 x 的反方向
{
    if(x==0) return 2;
    if(x==2) return 0;
    if(x==1) return 3;
    return 1;
}
bool check(Node x,int dir)
{
    return mp[x.x+fx[dir][0]][x.y+fx[dir][1]]&&bk[mp[x.x+fx[dir][0]][x.y+fx[dir][1]]][R(dir)];
}
void dfs(Node now,int dir)
{
    if(dir==847)
    {
        for(int i=0;i<4;i++)
        {
            if(bk[mp[now.x+fx[i][0]][now.y+fx[i][1]]][R(i)])
                dfs({now.x+fx[i][0],now.y+fx[i][1]},i);
        }
    }
    if(!mp[now.x][now.y])//找到空缺
    {
        int _[5];
        char ans;
        for(int i=0;i<4;i++) _[i]=check(now,i);//和哪些方向联通
        if(_[0]&&_[1]&&_[2]&&_[3]) ans='+';
        else if(_[0]&&_[2]) ans='|';
        else if(_[1]&&_[3]) ans='-';
        else if(_[2]&&_[3]) ans='1';
        else if(_[0]&&_[3]) ans='2';
        else if(_[0]&&_[1]) ans='3';
        else ans='4';
        printf("%d %d ",now.x,now.y);
        cout << ans;
        exit(0);
    }
    if(mp[now.x][now.y]==7)
        dfs({now.x+fx[dir][0],now.y+fx[dir][1]},dir);
    else
    {
        for(int i=0;i<4;i++)
        {
            if((i!=R(dir))&&bk[mp[now.x][now.y]][i])
                dfs({now.x+fx[i][0],now.y+fx[i][1]},i);
        }
    }
}
void init()
{
    //bk[i][j] 表示编号为 i 的管道的方向 j 是开口的
    bk[1][2]=bk[1][3]=1;
    bk[2][0]=bk[2][3]=1;
    bk[3][0]=bk[3][1]=1;
    bk[4][1]=bk[4][2]=1;
    bk[5][0]=bk[5][2]=1;
    bk[6][1]=bk[6][3]=1;
    bk[7][0]=bk[7][1]=bk[7][2]=bk[7][3]=1;
}
int main()
{
    init();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c;cin>>c;
            if(c=='M') st={i,j},mp[i][j]=-1;
            if(c=='Z') ed={i,j},mp[i][j]=-1;
            if(c>='1'&&c<='4') mp[i][j]=c-'0';
            if(c=='|') mp[i][j]=5;
            if(c=='-') mp[i][j]=6;
            if(c=='+') mp[i][j]=7;
        }
    }
    dfs(st,847);
}

有可能有一些小 bug，有 hack 欢迎指出。