Luobuyu's Blog

0%

37.解数独

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.4k 阅读时长 ≈ 1 分钟
解数独，使用位运算打标记。

37.解数独

题目描述：

略

数据范围：

题解：

解法一：略

解法二：舞蹈链

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    // 二进制优化
    // 分别表示 行 列 九宫格
    enum
    {
        ROW,
        COL,
        GRID
    };
    bool dfs(int step, vector<vector<int>> &vis, vector<vector<char>> &board)
    {
        if (step == 81)
            return true;
        int row = step / 9, col = step % 9, grid = row / 3 * 3 + col / 3;
        if (board[row][col] != '.')
        {
            return dfs(step + 1, vis, board);
        }

        for (int i = 1; i <= 9; ++i)
        {
            if (vis[ROW][row] & (1 << i) ||
                vis[COL][col] & (1 << i) ||
                vis[GRID][grid] & (1 << i))
                continue;
            board[row][col] = i + '0';
            vis[ROW][row] |= (1 << i);
            vis[COL][col] |= (1 << i);
            vis[GRID][grid] |= (1 << i);
            if (dfs(step + 1, vis, board))
                return true;
            else
            {
                board[row][col] = '.';
                vis[ROW][row] &= ~(1 << i);
                vis[COL][col] &= ~(1 << i);
                vis[GRID][grid] &= ~(1 << i);
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>> &board)
    {
        vector<vector<int>> vis(3, vector<int>(9, 0));
        // 打标记
        for (int i = 0, num; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] == '.')
                    continue;
                num = board[i][j] - '0';
                vis[ROW][i] |= (1 << num);
                vis[COL][j] |= (1 << num);
                vis[GRID][i / 3 * 3 + j / 3] |= (1 << num);
            }
        }
        dfs(0, vis, board);
    }
};