自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 22:01:32，当前版本为作者最后更新于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;
}

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