P7724 远古档案馆（Ancient Archive）

zuiyunlan · 2021-07-18 16:07:07 · 题解

P7724 远古档案馆（Ancient Archive）

原题链接

数据很弱，月赛三十多行过了，补充上所有情况后近百行，竟是道入门题。感谢 logfk 提供 Hack 数据。感谢 mrsrz 和 Anguei 两位管理的认真审核与纠错。

思路

题解中已经有朋友打了暴力搜索，我给出一种没有思维难度且代码量较少的 O(1) 解法吧。既然只有四个格子，我们可以找出所有不能移动到最终状态的情况，对输入数据进行逐个判断，如果最后仍不满足条件则可以移动到最终状态。

分析

设输入的两个 2 \times2 方格分别为 a_{1} \sim a_{4}，b_{1} \sim b_{4}。

首先，如果两个方格完全相同，不用移动，初始状态与最终状态就是相同的。判断是否满足这个条件，只需直接判断四个数字的位置是否完全相同，得出判断（封装成函数，后面会用到）：

bool same(){
    if(a[1]==b[1]&&a[2]==b[2]&&a[3]==b[3]&&a[4]==b[4]) return 1;
    return 0;
}
if(same()){
    printf("Yes"); 
    return 0;
}

题中已经说明网格中可能没有正整数，也可能没有空格，其中没有正整数的情况，即四个数字全部为零，第一条判断语句已经解决了。当网格中没有空格时，分为两种情况：

两个方格完全相同，第一条判断已经解决，不必考虑。
两个方格不同，一定无法移动到最终状态。

只考虑第二种情况，没有空格即四个数字全部不为零。用变量 num 记录网格中空格个数，如果其值为零，没有空格。得出判断：

if(num==0){
    printf("No"); 
    return 0;
}

暂且跳过只有一个空格的情况，存在两个空格时，又可以分为两种情况，如图：

观察第一种情况，将方格记为 (2,3,0,0)，只需要将“2”，“3”向下移动，就能将其转化为 (0,0,2,3)，同理第二种情况 (2,0,0,3) 可以转化为 (0,2,3,0)，且可以移动到任意状态。而存在三个空格时，唯一的非零数字可以任意移动。可得一条结论：

如果存在两个及以上空格，一定能够移动到最终状态。

已经用 num 存储空格个数，得出判断：

if(num>=2){
    printf("Yes");
    return 0;
}

以下结论仅适用于只存在一个空格，且两个方格不完全相同的情况。

如果只有一个空格，一定有两个非空格与它相邻，分别从两个非空格开始移动，如图：

我们发现，这两种移动方式实际上分别是除空格外数列绕方格的顺时针旋转与逆时针旋转。图中标红数据即为数列旋转一百八十度的结果。运用小学数学关于旋转的知识，不难想到：初始状态最后一行与最终状态的第一行可能是相反的（如上图 2,3 和 3,2）那么最后一行与第一行一定是相反的吗？如图：

图中数据 (5,0,3,2) 最后一行与初始状态 (2,3,5,0) 第一行同为 5,0，但很明显，初始状态可以移动到最终状态。为什么？不要忘记，数列并不是作为一个整体在方格中旋转，其中可能有一个数字“掉队”，看看图一中的“5”，如果它向右走一格后将方格旋转一百八十度，便能得到最终状态。

当 a 的第二行与 b 的第一行相同的情况时，有两种情况：

a 的第一行与 b 的第二行相反。
a 的第一行与 b 的第二行相同。

第一种情况，这时如果 a 的第二行中有一个数字“掉队”，即 a 的第二行中存在 “0” 时，将第二行的非零数字移到空格位置，恰好是 b 旋转一百八十度后结果。我们只要在判断两行相同的基础上，再次判断该行中是否含有空格即可。第二种情况，两个方格上下颠倒，只要进行一次对（a 的第一行与 b 的第二行）的判断，一次对（a 的第二行与 b 的第一行）的判断，由于目前只含有一个空格，不在第一行就在第二行，不必考虑。同理得出函数：

bool judge1(){
    if(a[1]==b[3]&&a[2]==b[4]){
        if(a[1]!=0&&a[2]!=0) return 1;
    }
    if(a[3]==b[1]&&a[4]==b[2]){
        if(a[3]!=0&&a[4]!=0) return 1;
    }
    if(a[1]==b[2]&&a[3]==b[4]){
        if(a[1]!=0&&a[3]!=0) return 1;
    }
    if(a[2]==b[1]&&a[4]==b[3]){
        if(a[2]!=0&&a[4]!=0) return 1;
    }
    return 0;
}

理解“掉队”情况后，再次观察图中标绿数据，如图：

两个方格第一行是相同的，第二行的“2”却慢了一步。幸好“2”的前方是一个空格，它能够跟上队伍。我们发现，如果两个方格第一行相同，只有第二行存在空格时，才能移动到最终状态，由于目前只含有一个空格，换句话说，如果第一行相同且其中含有空格，一定不能移动到最终状态。同理得出函数：

bool judge2(){
    if(a[1]==b[1]&&a[2]==b[2]){
        if(a[1]==0||a[2]==0) return 1;
    }
    if(a[3]==b[3]&&a[4]==b[4]){ 
        if(a[3]==0||a[4]==0) return 1;
    }
    if(a[1]==b[1]&&a[3]==b[3]){ 
        if(a[1]==0||a[3]==0) return 1;
    }
    if(a[2]==b[2]&&a[4]==b[4]){
        if(a[2]==0||a[4]==0) return 1;
    }
    return 0;
}

还没完，观察图中标蓝数据，如图：

方格顺时针旋转和逆时针旋转九十度分别得到图一、图二，很明显，图一可以通过旋转变为图二，假设 (5,2,0,3) 为初始状态，(3,0,2,5) 为最终状态，两个方格两组对角数字位置恰好是相反的。这时可以移动到最终状态。而在两个方格不完全相同且只含一个空格的情况下，如果一组对角数字位置相同，另一组对角数字位置一定相反。这时不能移动到最终状态。那么，当初始状态可以移动到最终状态时，每一组对角数字位置一定不同。得出函数：

bool judge3(){
    if(a[1]==b[1]&&a[4]==b[4]||a[2]==b[2]&&a[3]==b[3])return 1; 
    return 0;
}

如果我们只是将上文的判断组合起来，试试这组数据：

明显无法移动到最终状态，上文却并未提到这种情况，程序给出的答案是 "Yes"。观察两个方格，并没有找到规律。但仔细看看初始状态 (0,2,5,3)，不妨让 “2” 退到空格位置，初始状态就变成 (2,0,5,3)，与最终状态的第二列相同了。综合 judge1 函数，判断出无法移动到最终状态。

也就是说，第一次判断两个方格不满足以上条件时，不能直接得出正确的结论。初始状态中既然存在一个空格，就一定有两种情况：

空格位置为 “2” 或 “3”时，“1”、“4” 两格数字可以移到空格位置。
空格位置为 “1” 或 “4”时，“2”、“3” 两格数字可以移到空格位置。

读入数据后，记录空格个数，同时用变量 k 记录空格位置，判断哪两个位置的数字可以移至空格，接着判断以上条件是否成立，成立输出结束，不成立将数字移回原位置，移动另一个数字再次判断。需要注意，移动后两个方格可能完全相同。 这时一定能够移动到最终状态，所以需要判断前文的 same 函数不成立。得出函数：

bool move(int x){
    swap(a[k],a[x]); 
    if((judge1()||judge2()||judge3())&&!same()) return 1;
    else swap(a[k],a[x]);
    return 0;
}

Code

#include<iostream>
#include<cstdio>
using namespace std;
int a[5],b[5],num=0,k;
bool judge1(){
    if(a[1]==b[3]&&a[2]==b[4]){ //a的第一行与b的第二行相同 
        if(a[1]!=0&&a[2]!=0) return 1;
    }
    if(a[3]==b[1]&&a[4]==b[2]){ //a的第二行与b的第一行相同 
        if(a[3]!=0&&a[4]!=0) return 1;
    }
    if(a[1]==b[2]&&a[3]==b[4]){ //a的第一列与b的第二列相同
        if(a[1]!=0&&a[3]!=0) return 1;
    }
    if(a[2]==b[1]&&a[4]==b[3]){ //a的第二列与b的第一列相同 
        if(a[2]!=0&&a[4]!=0) return 1;
    }
    return 0;
}
bool judge2(){
    if(a[1]==b[1]&&a[2]==b[2]){ //a的第一行与b的第一行相同 
        if(a[1]==0||a[2]==0) return 1;
    }
    if(a[3]==b[3]&&a[4]==b[4]){ //a的第二行与b的第二行相同 
        if(a[3]==0||a[4]==0) return 1;
    }
    if(a[1]==b[1]&&a[3]==b[3]){ //a的第一列与b的第一列相同 
        if(a[1]==0||a[3]==0) return 1;
    }
    if(a[2]==b[2]&&a[4]==b[4]){ //a的第二列与b的第二列相同 
        if(a[2]==0||a[4]==0) return 1;
    }
    return 0;
}
bool judge3(){
    if(a[1]==b[1]&&a[4]==b[4]|| //a,b左上与右下相同 
       a[2]==b[2]&&a[3]==b[3]){ //a,b右上与左下相同 
         return 1;  
    }
    return 0;
}
bool same(){ //a,b四个格完全相同 
    if(a[1]==b[1]&&a[2]==b[2]&&a[3]==b[3]&&a[4]==b[4]) return 1;
     return 0;
}
bool move(int x){
    swap(a[k],a[x]); //x格中数字移到空格位置 
    if((judge1()||judge2()||judge3())&&!same()) return 1;
    else swap(a[k],a[x]); //判断不成立，数字回到x格
    return 0;
}
int main(){
    scanf("%d %d %d %d",&a[1],&a[2],&a[3],&a[4]);
    scanf("%d %d %d %d",&b[1],&b[2],&b[3],&b[4]);
    for(int i=1;i<=4;i++){
        if(a[i]==0){
            num++; //记录空格个数 
            k=i; //记录空格出现位置 
        }
    }
    if(same()){ //四个格全部相同
        printf("Yes"); 
        return 0;
    }
    if(num==0){ //四个格全部不为空
        printf("No"); 
        return 0;
    }
    if(num>=2){ //空格个数两个及以上 
        printf("Yes");
        return 0;
    }
    //以下均为只存在一个空格的情况 
    if(judge1()||judge2()||judge3()){ //判断
        printf("No");
        return 0;
    }
    if(k==2||k==3){ //空格位置为2或3时 
    if(move(1)||move(4)){ //判断1,4格中数字移到空格位置时 
        printf("No");
        return 0;
        }
    }
    if(k==1||k==4){ //空格位置为1或4时
    if(move(2)||move(3)){ //判断2,3格中数字移到空格位置时  
        printf("No");
        return 0;
        } 
    }
    printf("Yes"); //全部不成立，结束 
    return 0;
}