洛谷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;
}