首页 > 代码库 > LeetCode: Valid Sudoku [035]
LeetCode: Valid Sudoku [035]
【题目】
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.
【题意】
判断一个数独是否合法。一个合法的数独要求:每行、每列、9个小九宫格中都只能填充1~9九个数字各一次。
【思路】
1. 为每一行建一个行访问标记数组2. 为每一列建一个列访问标记数组
3. 为每个九宫格建一个访问标记数组
扫描数独矩阵,凡是有数字填充的在相应的访问数组中标记,如果发现有重复标记的,则返回false
【代码】
class Solution { public: bool isValidSudoku(vector<vector<char> > &board) { vector<vector<bool> > rows(9, vector<bool>(9, false)); vector<vector<bool> > cols(9, vector<bool>(9, false)); vector<vector<bool> > blocks(9, vector<bool>(9, false)); for(int i=0; i<9; i++){ for(int j=0; j<9; j++){ if(board[i][j]==‘.‘)continue; //判断行 if(rows[i][board[i][j]-‘0‘-1])return false; else rows[i][board[i][j]-‘0‘-1]=true; //判断列 if(cols[j][board[i][j]-‘0‘-1])return false; else cols[j][board[i][j]-‘0‘-1]=true; //判断block if(blocks[i/3*3+j/3][board[i][j]-‘0‘-1])return false; //注意block索引号的计算 else blocks[i/3*3+j/3][board[i][j]-‘0‘-1]=true; } } return true; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。