[LeetCode] Valid Sudoku
发布时间：2020-12-13 20:10:46 所属栏目：PHP教程 来源：网络整理
导读：Valid Sudoku Determine if a Sudoku is valid,according to:Sudoku Puzzles - The Rules. The Sudoku board could be partially filled,where empty cells are filled with the character '.' . A partially filled sudoku which is valid. Note: A valid S
|
Valid Sudoku Determine if a Sudoku is valid,according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled,where empty cells are filled with the character
A partially filled sudoku which is valid.
Note: 解题思路： 题意为验证数独的有效性。这里说的有效是值谜面的有效性，不包括是不是能够解出。数独的规则是，每行1⑼只出现1次，每列1⑼只出现1次，每个小9宫格1⑼只出现1次。顺次验证便可。1个圈套就是字符减的不是'0'，而是'1' class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
//验证每行是不是有效
for(int i=0; i<9; i++){
if(!checkRowValid(board,i)){
return false;
}
}
//验证每列是不是有效
for(int i=0; i<9; i++){
if(!checkColumnValid(board,i)){
return false;
}
}
//验证每格是不是有效
for(int i=0; i<9; i=i+3){
for(int j=0; j<9; j=j+3){
if(!checkGridValid(board,i,j)){
return false;
}
}
}
return true;
}
//验证每一个格是不是有效，传入的是左上角的下标
bool checkGridValid(vector<vector<char>>& board,int m,int n){
bool flag[9];
memset(flag,sizeof(bool)*9);
for(int i=m; i<m+3; i++){
for(int j=n; j<n+3; j++){
if(board[i][j]=='.'){
continue;
}
if(flag[board[i][j]-'1']){
return false;
}
flag[board[i][j]-'1']=true;
}
}
return true;
}
//验证每行是不是有效，传入的是行号
bool checkRowValid(vector<vector<char>>& board,int m){
bool flag[9];
memset(flag,sizeof(bool)*9);
for(int i=0; i<9; i++){
if(board[m][i]=='.'){
continue;
}
if(flag[board[m][i]-'1']){
return false;
}
flag[board[m][i]-'1']=true;
}
return true;
}
//验证每列是不是有效，传入的是列号
bool checkColumnValid(vector<vector<char>>& board,sizeof(bool)*9);
for(int i=0; i<9; i++){
if(board[i][n]=='.'){
continue;
}
if(flag[board[i][n]-'1']){
return false;
}
flag[board[i][n]-'1']=true;
}
return true;
}
}; （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
