P7185

· · 题解

P7185

UPDATE ON 2024/1/29

如果您 Subtask #1 过不去，请看本篇题解的 Hack 部分。

正文

刚好比赛时打到这一题，本蒟蒻就来发个题解。

显然，大部分人看到这一道题时想的思路是通过模拟管道送气的过程找出被删掉的构建块，即模拟算法。

其实，由题意可知：

整个 R 行 C 列的地图中有且只有一个格子满足是被黑客删掉的构建块，而且所有在地图上的构建块都不是是冗余的，即不会出现以下情况：

（下图中：红色表示构建块方向，黄色表示可能被删掉的格子，蓝色代表有冗余的构建块。）

有多个被删掉的格子

有冗余构建块

当然，以上情况均可归为有不止一个空白地块（即“.”地块）有管道与之相连。

所以我们可以遍历整个地图判断哪个空白地块与未连通的构建块相邻。

核心代码 1：

判断四个方向是否联通。

由题目中的图：

可知：

可得代码：（教练标程）


bool left( int r, int s ) {
   return s >  1  && (a[r][s-1]=='+' || a[r][s-1]=='-' || a[r][s-1]=='1' || a[r][s-1]=='2');
}
bool right( int r, int s ) {
   return s < S   && (a[r][s+1]=='+' || a[r][s+1]=='-' || a[r][s+1]=='3' || a[r][s+1]=='4');
}
bool up( int r, int s ) {
   return r >  1  && (a[r-1][s]=='+' || a[r-1][s]=='|' || a[r-1][s]=='1' || a[r-1][s]=='4');
}
bool down( int r, int s ) {
   return r < R   && (a[r+1][s]=='+' || a[r+1][s]=='|' || a[r+1][s]=='2' || a[r+1][s]=='3');
}

核心代码 2 与优化 1：

判断被删掉构建块的形态。

由上段，可得代码：（教练标程）

     if( left(r,s) && right(r,s) && up(r,s) && down(r,s) ) printf( "%d %d +\n", r, s );
else if( left(r,s) && right(r,s) ) printf( "%d %d -\n", r, s );
else if(  up (r,s) &&  down(r,s) ) printf( "%d %d |\n", r, s );
else if(right(r,s) &&  down(r,s) ) printf( "%d %d 1\n", r, s );
else if(right(r,s) &&   up (r,s) ) printf( "%d %d 2\n", r, s );
else if( left(r,s) &&   up (r,s) ) printf( "%d %d 3\n", r, s );
else if( left(r,s) &&  down(r,s) ) printf( "%d %d 4\n", r, s );

但是！这个代码需多次调用函数，不符合新时代 IOers 更快更短的追求，所以我们考虑状压。

给上、右、下、左分别附上 1、2、4、8 的权值来快速找出是哪种构建块。

从左起对应权值：5、10、15、6、3、9、12。

可得代码：（自己代码）


if(tot){
    printf("%d %d ",i,j);
         if(tot==5 )puts("|");
    else if(tot==10)puts("-");
    else if(tot==15)puts("+");
    else if(tot==6 )puts("1");
    else if(tot==3 )puts("2");
    else if(tot==9 )puts("3");
    else            puts("4");
    return 0;
}

Hack 与对策

我正在改题时，教练多加了两组 Hack，上面代码的分数降到了 81。

个人认为 Hack 与题意相悖，但是还是附上 Hack 与思路：

Hack 1：

Input：

1 3
M.Z

Output：

1 2 -

Hack 2：

Input：

2 3
M.Z
23.

Output：

1 2 1

思路：

第一遍搜索如果未搜出答案则进入第二次（注意考虑第一遍搜索时 Hack 2 中坐标为 (1,2) 的格子权值为 4，不要让它输出）。

并且在第一次搜索中预处理出 莫斯科 与 克罗地亚 是否有管道相邻（虽然题面说至少有一，但 Hack 没有）。

在第二次搜索中把 莫斯科 与 克罗地亚 当作管道（前提该城市是没有管道相邻）从而得出答案。

附代码：（码风很丑）


for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    if(ch[i][j]=='M'||ch[i][j]=='Z'){//       预处理 莫斯科 与 克罗地亚 是否作为管道
        if(i>1){
            if(ch[i][j]=='M')flagz&=(ch[i-1][j]=='.');
            else if(ch[i][j]=='Z')flagm&=(ch[i-1][j]=='.');
        }
        if(i<n){
            if(ch[i][j]=='M')flagz&=(ch[i+1][j]=='.');
            else if(ch[i][j]=='Z')flagm&=(ch[i+1][j]=='.');
        }
        if(j>1){
            if(ch[i][j]=='M')flagz&=(ch[i][j-1]=='.');
            else if(ch[i][j]=='Z')flagm&=(ch[i][j-1]=='.');
        }
        if(j<m){
            if(ch[i][j]=='M')flagz&=(ch[i][j+1]=='.');
            else if(ch[i][j]=='Z')flagm&=(ch[i][j+1]=='.');
        }
    }
    else if(ch[i][j]=='.'){
        tot=0;
        tmp=ch[i-1][j];
        cnt=tot+=(tmp=='+'||tmp=='|'||tmp=='1'||tmp=='4');
        tmp=ch[i][j+1];
        tot+=(tmp=='+'||tmp=='-'||tmp=='3'||tmp=='4')?2:0;cnt+=tot/2;
        tmp=ch[i+1][j];
        tot+=(tmp=='+'||tmp=='|'||tmp=='2'||tmp=='3')?4:0;cnt+=tot/4;
        tmp=ch[i][j-1];
        tot+=(tmp=='+'||tmp=='-'||tmp=='1'||tmp=='2')?8:0;cnt+=tot/8;

        //cnt 用于特判 Hack2

        if(tot&&(cnt+1)&1){
            printf("%d %d ",i,j);
            if(tot==10)puts("-");
            else if(tot==5)puts("|");
            else if(tot==15)puts("+");
            else if(tot==6)puts("1");
            else if(tot==3)puts("2");
            else if(tot==9)puts("3");
            else puts("4");
            return 0;
        }
    }
}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    if(ch[i][j]!='.')continue;
    tot=0;
    tmp=ch[i-1][j];tot+=(tmp=='+'||tmp=='|'||tmp=='1'||tmp=='4'||(flagm&&tmp=='Z')||(flagz&&tmp=='M'));
    tmp=ch[i+1][j];tot+=(tmp=='+'||tmp=='|'||tmp=='2'||tmp=='3'||(flagm&&tmp=='Z')||(flagz&&tmp=='M'))?4:0;
    tmp=ch[i][j-1];tot+=(tmp=='+'||tmp=='-'||tmp=='1'||tmp=='2'||(flagm&&tmp=='Z')||(flagz&&tmp=='M'))?8:0;
    tmp=ch[i][j+1];tot+=(tmp=='+'||tmp=='-'||tmp=='3'||tmp=='4'||(flagm&&tmp=='Z')||(flagz&&tmp=='M'))?2:0;
    if(tot){
        printf("%d %d ",i,j);
        if(tot==10)puts("-");
        else if(tot==5)puts("|");
        else if(tot==15)puts("+");
        else if(tot==6)puts("1");
        else if(tot==3)puts("2");
        else if(tot==9)puts("3");
        else puts("4");
        return 0;
    }
}

总代码：（非 Hack）

#include<iostream>
#include<cstdio>
using namespace std;
char ch[26][26],tmp;int n,m,tot;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",ch[i]+1);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(ch[i][j]!='.')continue;tot=0;
        tmp=ch[i-1][j];if(tmp=='+'||tmp=='|'||tmp=='1'||tmp=='4')tot+=1;
        tmp=ch[i+1][j];if(tmp=='+'||tmp=='|'||tmp=='2'||tmp=='3')tot+=4;
        tmp=ch[i][j-1];if(tmp=='+'||tmp=='-'||tmp=='1'||tmp=='2')tot+=8;
        tmp=ch[i][j+1];if(tmp=='+'||tmp=='-'||tmp=='3'||tmp=='4')tot+=2;
        if(tot){
            printf("%d %d ",i,j);
            if(tot==10)puts("-");
            else if(tot==5)puts("|");
            else if(tot==15)puts("+");
            else if(tot==6)puts("1");
            else if(tot==3)puts("2");
            else if(tot==9)puts("3");
            else puts("4");
            return 0;
        }
    }
    return 0;
}

校内 oj 实测 13 ms，760 b，最短第四快。

这是本蒟蒻的第一篇题解，如题解有解释不清等错误请见谅，也欢迎各位大佬提意见或建议。