C++ 有效的独数

C++ 有效的独数

  请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 ‘.’ 表示。

示例1

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
1
2
3
4
5
6
7
8
9
10
11

示例2

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
1
2
3
4
5
6
7
8
9
10
11
12

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字（1-9）或者 '.'

思路/解法

方式一

暴力穷举遍历即可。

class Solution 
{
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        vector<int> rowVisited(10, 0);
        vector<int> columnVisited(10, 0);
        vector<int> palaceVisited(10, 0);

        int  curIndex    = 0;
        bool status      = true;
        char rowChar;
        char columnChar;


        //行 列
        while(curIndex < 9)
        {
            for(int i = 0;i < 9;i++)
            {
                rowChar    = board[curIndex][i];
                columnChar = board[i][curIndex];

                if('.' != rowChar)
                {
                    if(1 == rowVisited[rowChar - 48])
                    {
                        status = false;
                        break;
                    }
                    rowVisited[rowChar - 48]++;
                }

                if('.' != columnChar)
                {
                    if(1 == columnVisited[columnChar - 48])
                    {
                        status = false;
                        break;
                    }
                    columnVisited[columnChar - 48]++;
                }
            }

            if(!status)
            {
                return false;
            }

            curIndex++;
            for(int i = 0;i < 10;i++)
            {
                rowVisited[i]    = 0;
                columnVisited[i] = 0;
            }
        }

        //3 x 3宫内
        for(int i = 0;i < 9;i += 3)
        {
            for(int j = 0;j < 9;j += 3)
            {
                for(int w = 0;w < 10;w++)
                {
                    palaceVisited[w] = 0;
                }

                for(int k = i;k < i + 3;k++)
                {
                    for(int z = j;z < j + 3;z++)
                    {
                        if('.' != board[k][z])
                        {
                            if(1 == palaceVisited[board[k][z] - 48])
                            {
                                status = false;
                                break;
                            }
                            palaceVisited[board[k][z] - 48]++;
                        }
                    }

                    if(!status)
                    {
                        break;
                    }
                }

                if(!status)
                {
                    break;
                }
            }

            if(!status)
            {
                break;
            }
        }



        return status;
    }
};
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

方式二

优化方式一，将3x3宫内判断与行列判断一起，只需通过 j/3 + (i/3)*3区分不同的宫格即可。

具体可参考：

作者：liujin-4
链接：https://leetcode.cn/problems/valid-sudoku/solution/36-jiu-an-zhao-cong-zuo-wang-you-cong-shang-wang-x/

class Solution 
{
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        vector<int>         rowVisited(10, 0);
        vector<int>         columnVisited(10, 0);
        vector<vector<int>> palaceVisited(10, vector<int>(10, 0));

        int  curIndex    = 0;
        bool status      = true;
        char rowChar;
        char columnChar;

        while(curIndex < 9)
        {
            for(int i = 0;i < 9;i++)
            {
                //行 列
                rowChar    = board[curIndex][i];
                columnChar = board[i][curIndex];

                if('.' != rowChar)
                {
                    if(1 == rowVisited[rowChar - 48])
                    {
                        status = false;
                        break;
                    }
                    rowVisited[rowChar - 48]++;

                    // 3 x 3宫内
                    if(palaceVisited[i / 3 + (curIndex /3) * 3][rowChar - 48])
                    {
                        status = false;
                        break;
                    }
                    palaceVisited[i / 3 + (curIndex /3) * 3][rowChar - 48]++;
                }

                if('.' != columnChar)
                {
                    if(1 == columnVisited[columnChar - 48])
                    {
                        status = false;
                        break;
                    }
                    columnVisited[columnChar - 48]++;
                }
            }

            if(!status)
            {
                break;
            }

            curIndex++;
            for(int i = 0;i < 10;i++)
            {
                rowVisited[i]    = 0;
                columnVisited[i] = 0;
            }
        }
        return status;
    }
};
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
66