[洛谷1274]魔术数字游戏 题解

前言

至少在洛谷2019年7月10日和之前，我拥有不打表程序中的 rank 1 提交记录
神奇的提交记录
吐槽一下样例，它是不完整的。

题解

首先为了方便计算我们显然要把一个格子的两个坐标压成一个整数。
具体计算方法将((i,j))转换为((i-1) imes4+j-1)。
这里我来介绍一种比较简洁的打法，首先我们打表预处理出所有的互相影响的块。
它长得像这样(由于4个角落的条件与中间4个的条件和对角线的条件冲突，所以不用考虑了):

int b[15][4] = {
    //row
    {0, 1, 2, 3},
    {4, 5, 6, 7},
    {8, 9, 10, 11},
    {12, 13, 14, 15},
    //col
    {0, 4, 8, 12},
    {1, 5, 9, 13},
    {2, 6, 10, 14},
    {3, 7, 11, 15},
    //djx
    {0, 5, 10, 15},
    {3, 6, 9, 12},
    //mid
    {5, 6, 9, 10},
    //block
    {0, 1, 4, 5},
    {2, 3, 6, 7},
    {8, 9, 12, 13},
    {10, 11, 14, 15}
    //jl
    //{0, 3, 12, 15}
};

在手算的时候注意让每个块内的四个元素从小到大排列，或者说至少最大的在最后，那么我们计算到每块第四个元素的时候，就可以直接计算了。
然后预处理每个元素是否能够被剪枝。

for (int i = 0; i < 15; ++i)
    xz[b[i][3]][cnt[b[i][3]]++] = i;

然后我们接下来直接DFS，当搜索到一个格子的时候，首先将它置为0。
开一个vis数组避免数字选择重复。
(pos1)表示题目限制的数字(1)的位置。
然后就珂以这样来判断剪枝:

a[num] = 0;
for (int i = 0; i < cnt[num]; ++i){
    if (!a[num]){
        a[num] = 34 - a[b[xz[num][i]][0]] - a[b[xz[num][i]][1]] - a[b[xz[num][i]][2]];
        if (a[num] > 16 || a[num] < 1) return ;
        if (a[num] == 1 && num != pos1) return ;
        if (vis[a[num]]) return ;
    }
    else{
        if (a[num] != 34 - a[b[xz[num][i]][0]] - a[b[xz[num][i]][1]] - a[b[xz[num][i]][2]]) return ;
    }
}

然后如果(a[num])还没有值就枚举(为了提高效率在(pos1)特殊处理)。

if (num == pos1){
    if (vis[1]) return ;
    vis[1] = 1; a[num] = 1;
    DFS(num + 1);
    vis[1] = 0;
}
else{
    for (int i = 2; i <= 16; ++i){
        if(vis[i]) continue;
        vis[i] = 1; a[num] = i;
        DFS(num + 1);
        vis[i] = 0;
    }
}

否则直接继续搜索。

整个主体和构思非常简洁明了。
然后一遍AC完结撒花！

代码

没有压行，所以较长。

#include <cstdio>

int b[15][4] = {
    //row
    {0, 1, 2, 3},
    {4, 5, 6, 7},
    {8, 9, 10, 11},
    {12, 13, 14, 15},
    //col
    {0, 4, 8, 12},
    {1, 5, 9, 13},
    {2, 6, 10, 14},
    {3, 7, 11, 15},
    //djx
    {0, 5, 10, 15},
    {3, 6, 9, 12},
    //mid
    {5, 6, 9, 10},
    //block
    {0, 1, 4, 5},
    {2, 3, 6, 7},
    {8, 9, 12, 13},
    {10, 11, 14, 15}
    //jl
    //{0, 3, 12, 15}
};

int a[16];
int vis[17];
int xz[16][10];
int cnt[16];
int pos1;

void DFS(int num){
    if (num == 16){
        if (a[pos1] != 1) return ;
        for (int i = 0; i < 4; ++i) printf("%d%c", a[i], ((i == 3) ? '
' : ' '));
        for (int i = 4; i < 8; ++i) printf("%d%c", a[i], ((i == 7) ? '
' : ' '));
        for (int i = 8; i < 12; ++i) printf("%d%c", a[i], ((i == 11) ? '
' : ' '));
        for (int i = 12; i < 16; ++i) printf("%d%c", a[i], ((i == 15) ? '
' : ' '));
        puts("");
        return ;
    }
    a[num] = 0;
    for (int i = 0; i < cnt[num]; ++i){
        if (!a[num]){
            a[num] = 34 - a[b[xz[num][i]][0]] - a[b[xz[num][i]][1]] - a[b[xz[num][i]][2]];
            if (a[num] > 16 || a[num] < 1) return ;
            if (a[num] == 1 && num != pos1) return ;
            if (vis[a[num]]) return ;
        }
        else{
            if (a[num] != 34 - a[b[xz[num][i]][0]] - a[b[xz[num][i]][1]] - a[b[xz[num][i]][2]]) return ;
        }
    }
    if (!a[num]){
        if (num == pos1){
            if (vis[1]) return ;
            vis[1] = 1; a[num] = 1;
            DFS(num + 1);
            vis[1] = 0;
        }
        else{
            for (int i = 2; i <= 16; ++i){
                if(vis[i]) continue;
                vis[i] = 1; a[num] = i;
                DFS(num + 1);
                vis[i] = 0;
            }
        }
    }
    else{
        if (num == pos1 && a[num] != 1) return ;
        vis[a[num]] = 1;
        DFS(num + 1);
        vis[a[num]] = 0;
    }
}

int main(){
    int x, y; scanf("%d %d", &x, &y); pos1 = (x - 1) * 4 + y - 1;
    for (int i = 0; i < 15; ++i)
        xz[b[i][3]][cnt[b[i][3]]++] = i;
    DFS(0);
    return 0;
}