458
[LeetCode]36.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.
【題意】
假設一個數獨是有效的，則它符合數獨遊戲 規則（點擊打開鏈接）。
數獨遊戲 規則：
（1）每一行都必須在1-9的範圍內，且隻出現一次。
（2）每一列都必須在1-9的範圍內，且隻出現一次。
（3）數字1-9在每個子宮格中隻出現一次。
數獨宮格可以部分填充，其中空單元格都充滿了字符'.'。
例如：
部分填充的有效數獨
【分析】
細節分析題
（1）檢查行
（2）檢查列
（3）檢查9個子宮格
【代碼】
/*********************************
* 日期：2014-01-20
* 作者：SJF0115
* 題號: Valid Sudoku
* 來源：https://oj.leetcode.com/problems/valid-sudoku/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
int i,j,k;
//判斷1-9是否已用
bool used[9];
for(i = 0;i < 9;i++){
//檢查行
memset(used,false,9);
for(j = 0;j < 9;j++){
//不符合規則
if(!check(board[i][j],used)){
return false;
}//if
}//for
//檢查列
memset(used,false,9);
for(j = 0;j < 9;j++){
//不符合規則
if(!check(board[j][i],used)){
return false;
}//if
}//for
}//for
//檢查9個子宮格
for(k = 0;k < 3;k++){
memset(used,false,9);
for(i = k*3;i < 3*k + 3;i++){
for(j = 0;j < 3;j++){
//不符合規則
if(!check(board[i][j],used)){
return false;
}//if
}//for
}//for
memset(used,false,9);
for(i = k*3;i < 3*k + 3;i++){
for(j = 3;j < 6;j++){
//不符合規則
if(!check(board[i][j],used)){
return false;
}//if
}//for
}//for
memset(used,false,9);
for(i = k*3;i < 3*k + 3;i++){
for(j = 6;j < 9;j++){
//不符合規則
if(!check(board[i][j],used)){
return false;
}//if
}//for
}//for
}//for
return true;
}
private:
bool check(char c,bool used[9]){
if(c == '.'){
return true;
}
//字符c 已用
if(used[c - '1']){
return false;
}
//字符c 未用
else{
used[c - '1'] = true;
return true;
}
}
};
int main() {
Solution solution;
bool result;
vector<vector<char>> board;
char value[9] = {'5','3','.','.','7','.','.','.','.'};
vector<char> subBoard(value,value + 9);
board.push_back(subBoard);
value = {'6','.','.','1','9','5','.','.','.'};
vector<char> subBoard1(value,value + 9);
board.push_back(subBoard1);
value = {'.','9','8','.','.','.','.','6','.'};
vector<char> subBoard2(value,value + 9);
board.push_back(subBoard2);
value = {'8','.','.','.','6','.','.','.','3'};
vector<char> subBoard3(value,value + 9);
board.push_back(subBoard3);
value = {'4','.','.','8','.','3','.','.','1'};
vector<char> subBoard4(value,value + 9);
board.push_back(subBoard4);
value = {'7','.','.','.','2','.','.','.','6'};
vector<char> subBoard5(value,value + 9);
board.push_back(subBoard5);
value = {'.','6','.','.','.','.','2','8','.'};
vector<char> subBoard6(value,value + 9);
board.push_back(subBoard6);
value = {'.','.','.','4','1','9','.','.','5'};
vector<char> subBoard7(value,value + 9);
board.push_back(subBoard7);
value = {'.','.','.','.','8','.','.','7','9'};
vector<char> subBoard8(value,value + 9);
board.push_back(subBoard8);
result = solution.isValidSudoku(board);
cout<<result<<endl;
return 0;
}
【代碼2】
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool used[9];
for (int i = 0; i < 9; ++i) {
fill(used, used + 9, false);
// 檢查行
for (int j = 0; j < 9; ++j){
if (!check(board[i][j], used)){
return false;
}//if
}//for
fill(used, used + 9, false);
// 檢查列
for (int j = 0; j < 9; ++j) {
if (!check(board[j][i], used)){
return false;
}//if
}//for
}//for
// 檢查 9 個子格子
for (int r = 0; r < 3; ++r) {
for (int c = 0; c < 3; ++c) {
fill(used, used + 9, false);
for (int i = r * 3; i < r * 3 + 3; ++i){
for (int j = c * 3; j < c * 3 + 3; ++j){
if (!check(board[i][j], used)){
return false;
}
}//for
}//for
}//for
}//for
return true;
}
bool check(char ch, bool used[9]) {
if (ch == '.') return true;
if (used[ch - '1']) return false;
used[ch - '1'] = true;
return true;
}
};
最後更新：2017-04-03 12:54:36