「题解」Solution P4573
做这道题的原因：上课教练给了一道这题的加强版，然后我就走入了一条不归路。
Description
给定一个 (9 imes 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) imes 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;
}
感谢您的阅读，希望对您有帮助