036有效的數獨

#include "000庫函數.h"

//一看，沒想出什么好法子，就遍歷了
//最重要的是如何比較小九宮格的數據
//44ms
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.')continue;
                for (int k = 8; k > j; --k)
                    if (board[i][j] == board[i][k])return false;//比較行        
                for (int k = 8; k > i; --k)
                    if (board[i][j] == board[k][j])return false;//比較列
                for (int k = i + 1; k % 3 != 0; k++) //比較九宮格
                    for (int h = j / 3 * 3; h < j / 3 * 3 + 3; h++)
                        if (board[i][j] == board[k][h])
                            return false;
            }
        return true;
    }
};


//博客答案
//使用容器，大大減少了循環次數，但大大增加了內存空間 
//36ms
class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        vector<vector<bool> > rowFlag(9, vector<bool>(9, false));//9*9用來標記行的
        vector<vector<bool> > colFlag(9, vector<bool>(9, false));//9*9用來標記列的
        vector<vector<bool> > cellFlag(9, vector<bool>(9, false));//9*9用來標記九宮格【共有9個】
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') continue;
                int c = board[i][j] - '1';
                if (rowFlag[i][c] || colFlag[c][j] || cellFlag[3 * (i / 3) + j / 3][c]) return false;
                //如果行或列或九宮已經被標記過，則出行重復
                rowFlag[i][c] = true;//進行標記
                colFlag[c][j] = true;
                cellFlag[3 * (i / 3) + j / 3][c] = true;//最好的就是這樣判斷哪個九宮格的位置，一直是困擾博主的一個地方
                
            }
        }
        return true;
    }
};

void T036() {

    vector<vector<char>> board;
    board = { {'.','.','5'},{'3','.','.'},{'.','.','3'} };
    Solution s;
    cout << s.isValidSudoku(board) << endl;

        

                
    

}

?