判断一个 9×9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
示例 1:
输入:
[
[“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
示例 2:
输入:
[
[“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 相同。
但由于位于左上角的 3×3 宫内有两个 8 存在, 因此这个数独是无效的。
#include <iostream> #include <vector> using namespace std; bool isvalidsudoku(vector<vector<char>>& board) { for(int i=0;i<9;i++)//判断行列是否有重复 { int a[256]={}; int a1[256]={}; for(int j=0;j<9;j++) { if(board[i][j]!='.') if(a[board[i][j]]==-1) return false; else a[board[i][j]]=-1; if(board[j][i]!='.') if(a1[board[j][i]]==-1) return false; else a1[board[j][i]]=-1; } } for(int i=0;i<9;i+=3)//判断小的宫格 { for(int j=0;j<9;j+=3) { int a[256]={}; for(int k=i;k<i+3;k++) { for(int h=j;h<j+3;h++) { if(board[k][h]!='.') if(a[board[k][h]]==-1) return false; else a[board[k][h]]=-1; } } } } return true; } int main() { // vector<vector<char>> 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'}}; // vector<vector<char>> 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'} // }; vector<vector<char>> board={{'.', '.', '.', '.', '5', '.', '.', '1', '.'}, {'.', '4', '.', '3', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '3', '.', '.', '1'}, {'8', '.', '.', '.', '.', '.', '.', '2', '.'}, {'.', '.', '2', '.', '7', '.', '.', '.', '.'}, {'.', '1', '5', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '2', '.', '.', '.'}, {'.', '2', '.', '9', '.', '.', '.', '.', '.'}, {'.', '.', '4', '.', '.', '.', '.', '.', '.'}}; bool ans=isvalidsudoku(board); std::cout << ans << std::endl; return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/604594.html