37. Sudoku Solver

https://leetcode.com/problems/sudoku-solver/description/

尝试所有可能性，DFS。需要三个visited set，看所在的box用二维的比较方便。

/*
 * @lc app=leetcode id=37 lang=cpp
 *
 * [37] Sudoku Solver
 */
class Solution {
public:
    bool dfs(int r, int c, vector<vector<char>> &board, vector<vector<bool>> &rows, vector<vector<bool>> &cols, vector<vector<vector<bool>>> &boxes) {
        if (c == 8) {
            if (r == 8) return true;
            r++;
            c = 0;
        } else ++c;
        if (board[r][c] != '.') return dfs(r, c, board, rows, cols, boxes);
        for (int i = 1; i <= 9; ++i) {
            if (!rows[r][i] && !cols[c][i] && !boxes[r / 3][c / 3][i]) {
                rows[r][i] = true;
                cols[c][i] = true;
                boxes[r / 3][c / 3][i] = true;
                board[r][c] = (char)('0' + i);
                if (dfs(r, c, board, rows, cols, boxes)) return true;     
                board[r][c] = '.';
                rows[r][i] = false;
                cols[c][i] = false;
                boxes[r / 3][c / 3][i] = false;  
            }
        }
        return false;
    }

    void solveSudoku(vector<vector<char>>& board) {
        vector<vector<bool>> rows(10, vector<bool>(10, false)), cols(rows);
        vector<vector<vector<bool>>> boxes(3, vector<vector<bool>>(3, vector<bool>(10, false)));
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') continue;
                const int num = board[i][j] - '0';
                rows[i][num] = true;
                cols[j][num] = true;
                boxes[i / 3][j / 3][num] = true;
            }
        }
        dfs(0, -1, board, rows, cols, boxes);
    }
};