[LeetCode] Valid Sudoku
來源：程序員人生 發(fā)布時(shí)間：2015-05-22 07:52:05 閱讀次數(shù)：3982次
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.
解題思路：
題意為驗(yàn)證數(shù)獨(dú)的有效性。這里說的有效是值謎面的有效性，不包括是不是能夠解出。數(shù)獨(dú)的規(guī)則是，每行1⑼只出現(xiàn)1次，每列1⑼只出現(xiàn)1次，每個(gè)小9宮格1⑼只出現(xiàn)1次。順次驗(yàn)證便可。1個(gè)圈套就是字符減的不是'0'，而是'1'
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
//驗(yàn)證每行是不是有效
for(int i=0; i<9; i++){
if(!checkRowValid(board, i)){
return false;
}
}
//驗(yàn)證每列是不是有效
for(int i=0; i<9; i++){
if(!checkColumnValid(board, i)){
return false;
}
}
//驗(yàn)證每格是不是有效
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;
}
//驗(yàn)證每一個(gè)格是不是有效，傳入的是左上角的下標(biāo)
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;
}
//驗(yàn)證每行是不是有效，傳入的是行號(hào)
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;
}
//驗(yàn)證每列是不是有效，傳入的是列號(hào)
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;
}
};
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
