洛谷P4573 [CQOI2013]新数独题解

题目链接：P4573 [CQOI2013]新数独

题意：

下面是一个没有数字，只有大小关系（没错，那些尖角都是“大于符号”）！的数独：

除了大小关系外（注意相邻格子不能相同），还需要满足通常的数独规则：

每个格子都是 $1\sim 9$ 的数字

每行都是 $1 \sim 9$ 的排列

每列都是 $1 \sim 9$ 的排列

每个 $3\times 3$ 的子矩阵（上图中用粗线隔开，一共有 $3\times 3$ 个这样的子矩阵）都是 $1\sim 9$ 的排列

为了美观，每个 $3\times 3$ 子矩阵的所有 $12$ 对相邻格子的大小关系都将给出。

输入格式：

一共 $15$ 行，包含一个新数独的实例。第 $1,3,5,6,8,10,11,13,15$ 行包含左右方向的符号（< 和 >），其余行包含上下方向的符号（^ 和 v）

输出格式：

包含 $9$ 行，每行 $9$ 个 $1\sim 9$ 的数字，以空格隔开。输入保证唯一解。

想了半天，感觉跟 topo 有啥关系，但是怎么看都会 T 。看了题解才发现做法是对的。。

题解里说这个题有加强版，而且可以卡到 3s 。所以碰上这种题只能莽了吗（大雾

回到正题。我们可以把大小关系看作边，不难发现建出来的图一定是个 DAG 。

我们把所有的点按照宫格、入度、行、列进行排序，然后暴搜。充其量就是个大搜索吧。

时间复杂度 $\mathcal{O}(\mathrm{ok})$

代码：（搬了题解的代码，~~有空再自己写吧~~）

#include <bits/stdc++.h>

using namespace std;

int Id(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 cmp(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 = Id(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, cmp); dfs(1);
    return 0;
}