题解 P4573 【[CQOI2013]新数独】

一只书虫仔 · 2020-11-22 11:10:06 · 题解

做这道题的原因：上课教练给了一道这题的加强版，然后我就走入了一条不归路。

本题链接 加强版链接

Description

给定一个 9 \times 9 的数独，并且每一个格子都与与他在同一个宫格里的数有大小关系，求填数独。

Solution 1

最简单的做法，直接 dfs。

先搞一个生成数独 dfs 出来，然后套进去输入。

输入如果嫌麻烦的话可以试试将所有行和列的大小关系存入数组，找一找规律不难发现，无论是上下还是左右关系，都是当编号不为 3 的倍数是才会有关系，并且先左右后上下，因此我们可以这么输入：

for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++) { // left and right
        if (j % 3 == 0) continue;
            scanf(" %c", &lvr[i][j]);
    }
    for (int j = 1; j <= 9; j++) { // up and down 
        if (i % 3 == 0) continue;
            scanf(" %c", &uvd[i][j]);
    }
}

然后在普通 dfs 生成数独的特判中套进去关系特判即可：

if (x > 1 && x - 1 % 3 != 0) {
    char tmp = uvd[x - 1][y];
    if (tmp == '^') 
        if (a[x - 1][y] > i) 
            continue;
    if (tmp == 'v')
        if (a[x - 1][y] < i)
            continue;
} // a[x - 1][y] & a[x][y]
if (y > 1 && y - 1 % 3 != 0) {
    char tmp = lvr[x][y - 1];
    if (tmp == '<')
        if (a[x][y - 1] > i)
                continue;
    if (tmp == '>')
        if (a[x][y - 1] < i)
            continue;
} // a[x][y - 1] & a[x][y]

dfs 生成数独的代码不放了，可以看看 这题。

然后用这个思路可以过本题，但是教练的加强版并过不了，只能获得 40 分的好成绩（

Solution 2

上面的代码我们是先按照行，再按照列的顺序进行枚举，一个格子只能最多判断两个关系，太浪费了。

因此我们可以先枚举宫格，再枚举行，再枚举列。

这块我们不能再采用二维 dfs 了，因为我们的思路是基于一个结构体排序。

创建一个结构体，编号为 cur 的点记录他的行，列和宫格。

按照排序的思路，也可以把排序函数写出来：

struct qaq {
    int Col;
    int Row;
    int Gongge;
} sudaku[90];

bool fjrakioi (qaq x, qaq y) {
    if (x.Gongge != y.Gongge) return x.Gongge < y.Gongge;
    else if (x.Col != y.Col) return x.Col < y.Col;
    else return x.Row < y.Row; 
} // fjr AK IOI !!!!!!!!!!!!!

需要修改的部分只有 dfs 中的特判边界条件（从 x>9 变为 cur>81）还有 dfs 内的当前局面变量（x,y 变为 cur，为了方便可以定义另定义 x,y 为 x = sudaku[cur].Col, y = sudaku[cur].Row），其他貌似并没有什么不一样，这个做法可以在加强版中获得 55 分的好成绩（

Solution 3

这道题是在我们学拓扑排序的时候给的，所以这题可以用上拓扑排序（

因为这题有不同格子之间的大小关系，所以我们可以将大小关系化为拓扑排序中的图的边（这个对于拓扑排序题来说挺套路的吧 qwq），然后在结构体中加上一个变量 tp 为这个格子在拓扑排序中的位置，然后按照宫格，tp，行，列的顺序进行排序：

struct qaq {
    int Col;
    int Row;
    int Gongge;
    int Tuopu;
} sudaku[90];

bool fjrakioi (qaq x, qaq y) {
    if (x.Gongge != y.Gongge) return x.Gongge < y.Gongge;
    else if (x.Tuopu != y.Tuopu) return x.Tuopu < y.Tuopu;
    else if (x.Col != y.Col) return x.Col < y.Col;
    else return x.Row < y.Row; 
}

转化图的时候有一点比较麻烦，就是图的点编号是一个一维的，但是数独矩阵是二维的，怎么转化呢？

教练把点转化为了二维，我觉得不必要，可以把格子的二维转化为一维，公式是 (x-1) \times 9+y，注意一下边界即可。

然后在 dfs 数独的特判中要从四个特判改成八个特判，因为你不知道你四周哪个点比你的拓扑排序位置靠前，所以干脆都特判一遍：

if (x > 1 && x - 1 % 3 != 0 && a[x - 1][y] != 0) {
    char tmp = uvd[x - 1][y];
        if (tmp == '^') 
            if (a[x - 1][y] > i) 
                continue;
        if (tmp == 'v')
            if (a[x - 1][y] < i)
                continue;
} // a[x - 1][y] & a[x][y]
if (y > 1 && y - 1 % 3 != 0 && a[x][y - 1] != 0) {
    char tmp = lvr[x][y - 1];
        if (tmp == '<')
            if (a[x][y - 1] > i)
                continue;
        if (tmp == '>')
            if (a[x][y - 1] < i)
                continue;
} // a[x][y - 1] & a[x][y]
if (x < 9 && x + 1 % 3 != 0 && a[x + 1][y] != 0) {
    char tmp = uvd[x + 1][y];
        if (tmp == '^') 
            if (a[x + 1][y] > i) 
                continue;
        if (tmp == 'v')
            if (a[x + 1][y] < i)
                continue;
} // a[x + 1][y] & a[x][y]
if (y < 9 && y + 1 % 3 != 0 && a[x][y + 1] != 0) {
    char tmp = lvr[x][y + 1];
        if (tmp == '<')
            if (a[x][y + 1] > i)
                continue;
        if (tmp == '>')
            if (a[x][y + 1] < i)
                continue;
} // a[x][y + 1] & a[x][y]

但是，这个代码仍然是 55，书虫一怒之下，求助了教练（

教练说可以加一步特判，即比如说这个格子 cur_1 比他上面的格子 cur_2 要大，那么如果确定了 cur_2，那么就不需要在 [1,9] 的区间里枚举 cur_1，在 [cur_2,9] 的区间里枚举 cur_1 即可，因此枚举 for 循环可以改一步：

int Max = -1;
if (x != 1 && a[x - 1][y] != 0 && uvd[x - 1][y] == '^') Max = max(Max, a[x - 1][y]);
if (x != 9 && a[x + 1][y] != 0 && uvd[x + 1][y] == 'v') Max = max(Max, a[x + 1][y]);
if (y != 1 && a[x][y - 1] != 0 && lvr[x][y - 1] == '<') Max = max(Max, a[x][y - 1]);
if (y != 9 && a[x][y + 1] != 0 && lvr[x][y + 1] == '>') Max = max(Max, a[x][y + 1]);
if (Max == -1) Max = 1;
for (int i = Max; i <= 9; i++)

然后，还是没卡过 55（

然后教练把时限开到了 5 秒
然后全机房的同学爽了一把，AC 了
然后我居然跑了个机房最优解（5.5s）smg
然后 fjr 5 秒的都没过 smg

Code

说了这么多，放一个教练加强版最慢点跑 3 秒多的代码吧：

#include <bits/stdc++.h>

using namespace std;

int zqzakioi (int x, int y) {
    return (x - 1) * 9 + y;
} 

int head[100]; 
int cnt;
int indeg[100];
int tuopu[100]; // index of tuopu
int Index;

struct node {
    int u, v;
} e[100];

void AddEdge (int u, int v) {
    e[++cnt].u = v;
    e[cnt].v = head[u];
    head[u] = cnt;
}

int Box[11][11] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, 
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}
};

struct qaq {
    int Col;
    int Row;
    int Gongge;
    int Tuopu;
} sudaku[90];

bool fjrakioi (qaq x, qaq y) {
    if (x.Gongge != y.Gongge) return x.Gongge < y.Gongge;
    else if (x.Tuopu != y.Tuopu) return x.Tuopu < y.Tuopu;
    else if (x.Col != y.Col) return x.Col < y.Col;
    else return x.Row < y.Row; 
}

bool col[11][11]; // hang
bool row[11][11]; // lie
bool box[11][11]; // gongge

int a[11][11];

bool lvr[11][11]; // left and right
bool uvd[11][11]; // up and down

void dfs (int cur) {
    if (cur > 81) {
        for (int i = 1; i <= 9; i++)  {
            for (int j = 1; j <= 9; j++)
                printf("%d ", a[i][j]);
            puts("");
        } 
        exit(0);
    }
    int x = sudaku[cur].Col;
    int y = sudaku[cur].Row;
    int Max = -1;
    if (x != 1 && a[x - 1][y] != 0 && uvd[x - 1][y] == '^') Max = max(Max, a[x - 1][y]);
    if (x != 9 && a[x + 1][y] != 0 && uvd[x + 1][y] == 'v') Max = max(Max, a[x + 1][y]);
    if (y != 1 && a[x][y - 1] != 0 && lvr[x][y - 1] == '<') Max = max(Max, a[x][y - 1]);
    if (y != 9 && a[x][y + 1] != 0 && lvr[x][y + 1] == '>') Max = max(Max, a[x][y + 1]);
    if (Max == -1) Max = 1;
    for (int i = Max; i <= 9; i++) {
        if (col[x][i] == true) continue;
        if (row[y][i] == true) continue;
        if (box[Box[x][y]][i] == true) continue;
        if (x > 1 && x - 1 % 3 != 0 && a[x - 1][y] != 0) {
            char tmp = uvd[x - 1][y];
            if (tmp == '^') 
                if (a[x - 1][y] > i) 
                    continue;
            if (tmp == 'v')
                if (a[x - 1][y] < i)
                    continue;
        } // a[x - 1][y] & a[x][y]
        if (y > 1 && y - 1 % 3 != 0 && a[x][y - 1] != 0) {
            char tmp = lvr[x][y - 1];
            if (tmp == '<')
                if (a[x][y - 1] > i)
                    continue;
            if (tmp == '>')
                if (a[x][y - 1] < i)
                    continue;
        } // a[x][y - 1] & a[x][y]
        if (x < 9 && x + 1 % 3 != 0 && a[x + 1][y] != 0) {
            char tmp = uvd[x + 1][y];
            if (tmp == '^') 
                if (a[x + 1][y] > i) 
                    continue;
            if (tmp == 'v')
                if (a[x + 1][y] < i)
                    continue;
        } // a[x + 1][y] & a[x][y]
        if (y < 9 && y + 1 % 3 != 0 && a[x][y + 1] != 0) {
            char tmp = lvr[x][y + 1];
            if (tmp == '<')
                if (a[x][y + 1] > i)
                    continue;
            if (tmp == '>')
                if (a[x][y + 1] < i)
                    continue;
        } // a[x][y + 1] & a[x][y]
        a[x][y] = i;
        col[x][i] = true;
        row[y][i] = true;
        box[Box[x][y]][i] = true;
        dfs(cur + 1);
        col[x][i] = false;
        row[y][i] = false;
        box[Box[x][y]][i] = false;
        a[x][y] = 0;
    }
}

int main () {
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) { // left and right
            if (j % 3 == 0) continue;
            scanf(" %c", &lvr[i][j]);
        }
        for (int j = 1; j <= 9; j++) { // up and down 
            if (i % 3 == 0) continue;
            scanf(" %c", &uvd[i][j]);
        }
    }
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++) {
            int tmp = zqzakioi(i, j);
            if (j % 3 != 0 && lvr[i][j] == '<') AddEdge(tmp, tmp + 1), indeg[tmp + 1]++;
            if (j % 3 != 0 && lvr[i][j] == '>') AddEdge(tmp + 1, tmp), indeg[tmp]++;
            if (i % 3 != 0 && uvd[i][j] == '^') AddEdge(tmp, tmp + 9), indeg[tmp + 9]++;
            if (i % 3 != 0 && uvd[i][j] == 'v') AddEdge(tmp + 9, tmp), indeg[tmp]++;
        }
    queue <int> q;
    for (int i = 1; i <= 81; i++)
        if (indeg[i] == 0)
            q.push(i);
    while (!q.empty()) {
        int cur = q.front();
        tuopu[++Index] = cur;
        q.pop();
        for (int p = head[cur]; p; p = e[p].v) {
            int tmp = e[p].u;
            indeg[tmp]--;
            if (indeg[tmp] == 0) q.push(tmp);
        }
    }
    int cnt_c = 1, cnt_r = 0; 
    for (int i = 1; i <= 81; i++) {
        cnt_r++;
        if (cnt_r > 9) cnt_c++, cnt_r = 1;
        sudaku[i].Col = cnt_c;
        sudaku[i].Row = cnt_r;
        sudaku[i].Gongge = Box[cnt_c][cnt_r];
        int cnt_t;
        for (int j = 1; j <= 81; j++) 
            if (tuopu[j] == i) {
                cnt_t = i;
                break;
            }
        sudaku[i].Tuopu = cnt_t;
    }
    sort(sudaku + 1, sudaku + 82, fjrakioi);
    dfs(1);
    return 0;
}

感谢您的阅读，希望对您有帮助