[LeetCode] Valid Sudoku


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 Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

解题思路:

题意为验证数独的有效性。这里说的有效是值谜面的有效性,不包括是不是能够解出。数独的规则是,每行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, 0, 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, 0, 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, int n){
bool flag[9];
memset(flag, 0, 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;
}
};

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » [LeetCode] Valid Sudoku

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡