P7185题解

Spark_King · 2024-02-20 12:28:16 · 题解

P7185题解

这道题是真的肝，调了我一晚上。

题目大意

在一个 n\times m 的矩阵中通过在特定位置添加某一种管道使得图中从 M 到 Z 的路径联通且没有管道赘余。

当然题目保证数据有唯一解。

分析

这是一道十分《简单》的模拟题。

由于保证有唯一解并且没有管道赘余，于是我们可以从 M 或 Z 出发进行 BFS，只要在搜索途中发现有地方断开，那么这个地方就是缺少管道的地方，之后就可以根据该点周围的管道类型来输出答案。

就比如：

不难看出，图中 (3,4) 处缺少一个横向管道，依据是图中 (3,3) 所连接的位置是空的，且该点也应与 (3,5) 连接。

于是我们可以按照上述思路大致模拟一下。

不过这道题存在两个 Hack 数据，类似于以下两个特殊情况：

在图一中除了 M 和 Z 以外没有管道，所以这种情况下需要在这两个地点之间添加管道。图二中 (2,4) 点周围没有管道，但是有一个 Z 点，所以在这种情况下我们要将地点看作管道。

清楚了这些，我们就可以快乐地写代码了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m; 
char mp[30][30];
pair<ll,ll> M,Z;
struct node
{
    ll x,y;
};
queue<node> q;
ll dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
bool flag,b[30][30];
void op1(ll x,ll y)
{
    cout<<x+1<<" "<<y<<" ";
    bool f[4]={0,0,0,0};
    if(mp[x+1][y-1]=='M'||mp[x+1][y-1]=='Z'||mp[x+1][y-1]=='-'||mp[x+1][y-1]=='+'||mp[x+1][y-1]=='1'||mp[x+1][y-1]=='2') f[1]++;
    if(mp[x+2][y]=='M'||mp[x+2][y]=='Z'||mp[x+2][y]=='|'||mp[x+2][y]=='+'||mp[x+2][y]=='2'||mp[x+2][y]=='3') f[2]++;
    if(mp[x+1][y+1]=='M'||mp[x+1][y+1]=='Z'||mp[x+1][y+1]=='-'||mp[x+1][y+1]=='+'||mp[x+1][y+1]=='3'||mp[x+1][y+1]=='4') f[3]++;
    if(f[1]&&f[2]&&f[3]) cout<<"+";
    else if(f[1]) cout<<3; 
    else if(f[2]) cout<<"|";
    else if(f[3]) cout<<2;
    return;
}
void op2(ll x,ll y)
{
    cout<<x-1<<" "<<y<<" ";
    bool f[4]={0,0,0,0}; 
    if(mp[x-1][y-1]=='M'||mp[x-1][y-1]=='Z'||mp[x-1][y-1]=='-'||mp[x-1][y-1]=='+'||mp[x-1][y-1]=='1'||mp[x-1][y-1]=='2') f[1]++;
    if(x-2>0&&(mp[x-2][y]=='M'||mp[x-2][y]=='Z'||mp[x-2][y]=='|'||mp[x-2][y]=='+'||mp[x-2][y]=='1'||mp[x-2][y]=='4')) f[2]++;
    if(mp[x-1][y+1]=='M'||mp[x-1][y+1]=='Z'||mp[x-1][y+1]=='-'||mp[x-1][y+1]=='+'||mp[x-1][y+1]=='4'||mp[x-1][y+1]=='3') f[3]++;
    if(f[1]&&f[2]&&f[3]) cout<<"+";
    else if(f[1]) cout<<4;
    else if(f[2]) cout<<"|";
    else if(f[3]) cout<<1;
    return;
}
void op3(ll x,ll y)
{
    cout<<x<<" "<<y+1<<" ";
    bool f[4]={0,0,0,0};
    if(mp[x-1][y+1]=='M'||mp[x-1][y+1]=='Z'||mp[x-1][y+1]=='|'||mp[x-1][y+1]=='+'||mp[x-1][y+1]=='1'||mp[x-1][y+1]=='4') f[1]++;
    if(mp[x][y+2]=='M'||mp[x][y+2]=='Z'||mp[x][y+2]=='-'||mp[x][y+2]=='+'||mp[x][y+2]=='4'||mp[x][y+2]=='3') f[2]++;
    if(mp[x+1][y+1]=='M'||mp[x+1][y+1]=='Z'||mp[x+1][y+1]=='|'||mp[x+1][y+1]=='+'||mp[x+1][y+1]=='3'||mp[x+1][y+1]=='2') f[3]++;
    if(f[1]&&f[2]&&f[3]) cout<<"+";
    else if(f[1]) cout<<3;
    else if(f[2]) cout<<"-";
    else if(f[3]) cout<<4;
    return;
}
void op4(ll x,ll y)
{
    cout<<x<<" "<<y-1<<" ";
    bool f[4]={0,0,0,0};
    if(mp[x-1][y-1]=='M'||mp[x-1][y-1]=='Z'||mp[x-1][y-1]=='|'||mp[x-1][y-1]=='+'||mp[x-1][y-1]=='2'||mp[x-1][y-1]=='3') f[1]++;
    if(y-2>0&&(mp[x][y-2]=='M'||mp[x][y-2]=='Z'||mp[x][y-2]=='-'||mp[x][y-2]=='+'||mp[x][y-2]=='1'||mp[x][y-2]=='2')) f[2]++;
    if(mp[x+1][y-1]=='M'||mp[x+1][y-1]=='Z'||mp[x+1][y-1]=='|'||mp[x+1][y-1]=='+'||mp[x+1][y-1]=='2'||mp[x+1][y-1]=='3') f[3]++;
    if(f[1]&&f[2]&&f[3]) cout<<"+";
    else if(f[1]) cout<<2;
    else if(f[2]) cout<<"-";
    else if(f[3]) cout<<1;
    return;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            cin>>mp[i][j];
            if(mp[i][j]=='M') M.first=i,M.second=j,b[i][j]=1;
            if(mp[i][j]=='Z') Z.first=i,Z.second=j,b[i][j]=1; 
        }
    }
    for(ll i=1;i<=4;i++)
    {
        ll kx=M.first+dx[i],ky=M.second+dy[i];
        if(mp[kx][ky]=='.'||kx<=0||kx>n||ky<=0||ky>m) continue;
        if(mp[kx][ky]!='.')
        {
            flag=1;
            q.push({kx,ky});
        }
    }
    if(!flag)
    {
        for(ll i=1;i<=4;i++)
        {
            ll kx=Z.first+dx[i],ky=Z.second+dy[i];
            if(mp[kx][ky]=='.'||kx<=0||kx>n||ky<=0||ky>m) continue;
            if(mp[kx][ky]!='.')
            {
                flag=1;
                q.push({kx,ky});    
            }
        }
        if(!flag)
        {
            ll mx=M.first,my=M.second;
            ll zx=Z.first,zy=Z.second;
            if(zx==mx)
            {
                cout<<zx<<" "<<(zy+my)/2<<" -";
                return 0;
            }
            else if(zy==my)
            {
                cout<<(zx+mx)/2<<" "<<zy<<" |";
                return 0;
            }
        }
    }
    while(!q.empty())
    {
        ll x=q.front().x,y=q.front().y;
        q.pop();
        b[x][y]=1;
        if(mp[x][y]=='|')
        {
            if(mp[x+1][y]=='.')
            {
                op1(x,y);
                return 0;
            }
            if(mp[x-1][y]=='.')
            {
                op2(x,y);                   
                return 0;
            }
            if(b[x+1][y]==0) q.push({x+1,y});
            if(b[x-1][y]==0) q.push({x-1,y});
        }
        else if(mp[x][y]=='-')
        {
            if(mp[x][y+1]=='.')
            {
                op3(x,y);
                return 0;
            }
            if(mp[x][y-1]=='.')
            {
                op4(x,y);
                return 0;
            }
            if(b[x][y+1]==0) q.push({x,y+1});
            if(b[x][y-1]==0) q.push({x,y-1});
        }
        else if(mp[x][y]=='1')
        {
            if(mp[x][y+1]=='.')
            {
                op3(x,y);
                return 0;
            }
            if(mp[x+1][y]=='.')
            {
                op1(x,y);
                return 0;
            }
            if(b[x][y+1]==0) q.push({x,y+1});
            if(b[x+1][y]==0) q.push({x+1,y});
        }
        else if(mp[x][y]=='2')
        {
            if(mp[x-1][y]=='.')
            {
                op2(x,y);               
                return 0;
            }
            if(mp[x][y+1]=='.')
            {
                op3(x,y);
                return 0;
            }
            if(b[x][y+1]==0) q.push({x,y+1});
            if(b[x-1][y]==0) q.push({x-1,y});
        }
        else if(mp[x][y]=='3')
        {
            if(mp[x][y-1]=='.')
            {
                op4(x,y);                   
                return 0;
            }
            if(mp[x-1][y]=='.')
            {
                op2(x,y);               
                return 0;
            }
            if(b[x][y-1]==0) q.push({x,y-1});
            if(b[x-1][y]==0) q.push({x-1,y});
        }
        else if(mp[x][y]=='4')
        {
            if(mp[x][y-1]=='.')
            {
                op4(x,y);                   
                return 0;
            }
            if(mp[x+1][y]=='.')
            {
                op1(x,y);
                return 0;
            }
            if(b[x][y-1]==0) q.push({x,y-1});
            if(b[x+1][y]==0) q.push({x+1,y});
        }
        else if(mp[x][y]=='+')
        {
            if(mp[x][y-1]=='.')
            {
                op4(x,y);               
                return 0;
            }
            if(mp[x+1][y]=='.')
            {
                op1(x,y);
                return 0;
            }
            if(mp[x-1][y]=='.')
            {
                op2(x,y);                   
                return 0;
            }
            if(mp[x][y+1]=='.')
            {
                op3(x,y);
                return 0;
            }
            if(b[x][y+1]==0) q.push({x,y+1});
            if(b[x-1][y]==0) q.push({x-1,y});
            if(b[x][y-1]==0) q.push({x,y-1});
            if(b[x+1][y]==0) q.push({x+1,y});
        }
    }
    return 0;
}