【LeetCode 37】解数独

【题解】

回溯法搞一下。
用set和数组下标判重。

【代码】

class Solution {

public:

    set<int> myset[9];

    int hang[9][10],lie[9][10];

    bool dfs(vector<vector<char>>& board,int x,int y){

        if (y==9){

            x++;y = 0;

        }

        if (x==9){

            return true;

        }

        if (board[x][y]!='.'){

            return dfs(board,x,y+1);

        }

        for (int i = 1;i <= 9;i++){

            if (hang[x][i] || lie[y][i]) continue;

            int idx = (x/3)*3+y/3;

            if (myset[idx].find(i)!=myset[idx].end()) continue;

            hang[x][i] = lie[y][i] = 1;

            myset[idx].insert(i);

            char key = i+'0';

            board[x][y] = key;

            if (dfs(board,x,y+1)) return true;

            board[x][y] = '.';

            hang[x][i] = lie[y][i] = 0;

            myset[idx].erase(i);

        }

        return false;

    }

    void solveSudoku(vector<vector<char>>& board) {

        for (int i = 0;i < 9;i++) myset[i].clear();

        memset(hang,0,sizeof hang);memset(lie,0,sizeof lie);

        for (int i = 0 ;i < 9;i++)

            for (int j = 0;j < 9;j++)

                if (board[i][j]!='.'){

                    int x = board[i][j]-'0';

                    hang[i][x]=1;

                    lie[j][x] = 1;

                    int ti = i/3,tj = j/3;

                    int idx = ti*3+tj;

                    myset[idx].insert(x);

                }

        dfs(board,0,0);

    }

};

巴特西

【LeetCode 37】解数独

最新文章

热门文章