题解 P1274 【魔术数字游戏】

· · 题解

P1274 魔术数字游戏

一道深搜回溯题，过程代码判断的代码挺多的。

先说一下思路，从a_{1,1}开始深搜，然后到a_{1,2}，到a_{1,3}，到a_{1,4}。到了每行的最后一个数时就来到下一行，即a_{2,1}。

搜到a_{5,1}的时候就开始判断，（注意不是a_{4,4}，因为只有到a_{5,1}的时候a_{4,4}才有值。）如果判断全部符合要求就输出，否则就回溯重搜。

但是这样会超时，比如说，第一行的四个数分别是

1,2,3,4

这样肯定不符合要求，但是这个时候却要继续往下搜，这样就浪费了不少时间。

所以我们可以在每次深搜的时候就判断一次，如果不符合条件就这就return，这样就可以节省不少时间。

我们可以发现，如果每次深搜时都判断一次，而每次判断虽然时间复杂度是O(1)，（应该是吧，我不太清楚）但是常数巨大。

由于a_{4,4}是在最后一次深搜时才出现值的，所以之前可以不用判断一下四个需要用到a_{4,4}值的判断：

所以，我们可以在之前的判断少一上这5个判断，然后再写一个新的判断，包含这5个判断，这样常数就会大幅度减少，速度变快。

由于这题输出量较大，建议用printf，如果可以手写快输（快写）也是可以的，当然fwrite也可以。

附上我的垃圾快输（快写）（可能会出锅，我这题没试过）：

inline void write(int x)
{
    static char buf[15];
    static int len=-1;
    if(x<0)putchar('-'),x=-x;
    do buf[++len]=x%10,x/=10;while(x);
    while(len>=0)putchar(buf[len--]+'0');
}

附上完整的有详细注释的代码：

#include<bits/stdc++.h>
using namespace std;
int a[5][5],v[17],n,m;
//a[i][j]来记录位置[i,j]所存的数，v[i]存i是否用过，n和m如题 
int check(int x,int y)
{ 
    //这里不要把两个if改为一个，否则全错 
    //前一个if是判断要判断的数是否在那个范围以内
    //后一个if是看和是不是34，如果一个不是就直接返回0，说明该方案不行，需要回溯重搜 
    if(x>2||x==2&&y>=2)
        if(a[1][1]+a[1][2]+a[2][1]+a[2][2]!=34)return 0;//左上角2*2位置的数的和 
    if(x>2||x==2&&y==4)
        if(a[1][3]+a[1][4]+a[2][3]+a[2][4]!=34)return 0;//右上角2*2位置的数的和 
    if(x==4&&y>=2)
        if(a[3][1]+a[3][2]+a[4][1]+a[4][2]!=34)return 0;//左下角2*2位置的数的和 
    if(x>3||x==3&&y>=3)
        if(a[2][2]+a[2][3]+a[3][2]+a[3][3]!=34)return 0;//中央的2*2位置的数的和 
    if(x>1||x==1&&y>=4)
        if(a[1][1]+a[1][2]+a[1][3]+a[1][4]!=34)return 0;//第一行所有数的和 
    if(x>2||x==2&&y>=4)
        if(a[2][1]+a[2][2]+a[2][3]+a[2][4]!=34)return 0;//第二行所有数的和 
    if(x>3||x==3&&y>=4)
        if(a[3][1]+a[3][2]+a[3][3]+a[3][4]!=34)return 0;//第三行所有数的和 
    if(x==4&&y>=1)
        if(a[1][1]+a[2][1]+a[3][1]+a[4][1]!=34)return 0;//第一列所有数的和 
    if(x==4&&y>=2)
        if(a[2][1]+a[2][2]+a[2][3]+a[2][4]!=34)return 0;//第二列所有数的和 
    if(x==4&&y>=3)
        if(a[3][1]+a[3][2]+a[3][3]+a[3][4]!=34)return 0;//第三列所有数的和 
    if(x==4&&y>=1)
        if(a[1][4]+a[2][3]+a[3][2]+a[4][1]!=34)return 0;//左下到右上对角线所有数的和 
    return 1;
} 
int check1()//搜完了，所有位置肯定都有数了，所以不必传参数x，y 
{
    if(a[1][1]+a[1][4]+a[4][1]+a[4][4]!=34)return 0;//四个角的数的和 
    if(a[3][3]+a[3][4]+a[4][3]+a[4][4]!=34)return 0;//右下角2*2位置的数的和 
    if(a[4][1]+a[4][2]+a[4][3]+a[4][4]!=34)return 0;//第四行所有数的和 
    if(a[1][4]+a[2][4]+a[3][4]+a[4][4]!=34)return 0;//第四列所有数的和 
    if(a[1][1]+a[2][2]+a[3][3]+a[4][4]!=34)return 0;//左上到右下对角线所有数的和 
    return 1;//如果所有都满足就返回1 
}
void dfs(int x,int y)
{
    if(x==5&&y==1&&check1())
    {
        for(int i=1;i<=4;i++)//输出 
        {
            for(int j=1;j<=4;j++)
                printf("%d ",a[i][j]);//printf较快 
            putchar('\n');//putchar较快 
        }
        putchar('\n');//还要再换一次行 
        return;//答案输出后就可以返回了 
    }
    if(a[x][y])//如果当前这个位置有数了 
        if(y==4)dfs(x+1,1);//如果到了一行中的最后一个位置，那就到下一行继续搜 
        else dfs(x,y+1);//否则就再往下一个数搜
    else//如果没有数 
    {
        if(y==1)x--,y=4;//如果是一行的第一个位置，就返回到上一行的最后一个位置搜 
        else y--;//否则就退到前一个位置 
        if(!check(x,y))return;//如果不符合，就可以直接return了 
        if(y==4)x++,y=1;//如果是一行中最后一个数，就来到下一行第一个数 
        else y++;//否则就来到下一个位置 
        for(int i=2;i<=16;i++)//继续深搜 
            if(!v[i])//如果当前这个数没有用过 
            {
                v[i]=1;//标记这个数用过了 
                a[x][y]=i;//当前位置的数为 i 
                if(y==4)dfs(x+1,1);//如果到了一行中最后一个位置，就来到下一行 
                else dfs(x,y+1);//否则就来到同一行下一个位置 
                a[x][y]=v[i]=0;//回溯时清零 
            }
    }
}
int main()
{
    cin>>n>>m;//输入n和m 
    a[n][m]=v[1]=1;//a[n][m]的值为1，且标记用过1这个数 
    dfs(1,1);//从第一行第一个数开始搜 
    return 0;//结束 
}

平均速度2s左右，应该是非打表（一点也算）中比较快的。（吐槽一下，本题的rank\;1是打表过的……）代码也很短，去掉注释1.73KB，而且还没有用三目运算符之类的。比

无注释代码我放这里，仅供参考。

谢谢观赏，麻烦点个赞犒劳一下……