首页 > 代码库 > 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.
注意:其中没有填的也代表有效的,用‘.‘表示。为了是每行每列以及每个9方格中没有重复的元素,使用了set来存放,本来想用map的,但是map每次要存放两个元素,多余。
当每行或每列填满之后,可以直接判断set的长度是否为9,否则就是有重复的元素。
C++代码如下:
#include<iostream>#include<set>#include<vector>using namespace std;class Solution{public: bool isValidSudoku(vector<vector<char> > &board) { set<char> st; size_t dot=0; int i,j; for(i=0; i<9; i++) { st.clear(); dot=0; for(j=0; j<9; j++) { if(board[i][j]==‘.‘) { dot++; continue; } st.insert(board[i][j]); } if(st.size()<9-dot) return false; } for(i=0; i<9; i++) { st.clear(); dot=0; for(j=0; j<9; j++) { if(board[j][i]==‘.‘) { dot++; continue; } st.insert(board[j][i]); } if(st.size()<9-dot) return false; } int block=0; for(block=0; block<9; block++) { dot=0; st.clear(); for(i=block/3*3; i<block/3*3+3; i++) { for(j=block%3*3; j<block%3*3+3; j++) { if(board[i][j]==‘.‘) { dot++; continue; } st.insert(board[i][j]); } } if(st.size()<9-dot) return false; } return true; }};int main(){ Solution s; /*vector<vector<char> > vec= {{‘8‘,‘1‘,‘4‘,‘6‘,‘5‘,‘2‘,‘7‘,‘3‘,‘9‘}, {‘9‘,‘5‘,‘7‘,‘1‘,‘8‘,‘3‘,‘6‘,‘2‘,‘4‘}, {‘2‘,‘3‘,‘6‘,‘9‘,‘7‘,‘4‘,‘1‘,‘5‘,‘8‘}, {‘6‘,‘9‘,‘5‘,‘4‘,‘3‘,‘7‘,‘2‘,‘8‘,‘1‘}, {‘4‘,‘8‘,‘1‘,‘5‘,‘2‘,‘6‘,‘3‘,‘9‘,‘7‘}, {‘3‘,‘7‘,‘2‘,‘8‘,‘9‘,‘1‘,‘5‘,‘4‘,‘6‘}, {‘5‘,‘6‘,‘9‘,‘3‘,‘1‘,‘8‘,‘4‘,‘7‘,‘2‘}, {‘7‘,‘4‘,‘8‘,‘2‘,‘6‘,‘5‘,‘9‘,‘1‘,‘3‘}, {‘1‘,‘2‘,‘3‘,‘7‘,‘4‘,‘9‘,‘8‘,‘6‘,‘5‘} };*/ vector<vector<char> >vec= {{‘.‘,‘.‘,‘5‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘6‘}, {‘.‘,‘.‘,‘.‘,‘.‘,‘1‘,‘4‘,‘.‘,‘.‘,‘.‘}, {‘2‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘}, {‘1‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘}, {‘5‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘}, {‘6‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘}, {‘7‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘}, {‘8‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘}, {‘9‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘,‘.‘}, }; cout<<s.isValidSudoku(vec)<<endl;}
Valid Sudoku
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。