C++ backtrack solution


  • 0
    X
    class Solution {
    public:
        void backtrack(int depth, vector<long long int>& path,
                       vector<bool>& visity, vector<bool>& visit1, vector<bool>& visit2,
                       vector<vector<string>>& ans, int n){
            if(depth == n){
                vector<string> tmp(n, string(n, '.'));
                for(long long int p : path){
                    int x = p / n;
                    int y = p % n;
                    tmp[x][y] = 'Q';
                }
                ans.push_back(tmp);
                return;
            }
            for(int j = 0; j < n; ++j){
                if(visity[j] || visit1[depth + j] || (visit2[depth - j + n - 1])){
                    continue;
                }
                visity[j] = true;
                visit1[depth + j] = true;
                visit2[depth - j + n - 1] = true;
                path.push_back(depth * n + j);
                backtrack(depth + 1, path, visity, visit1, visit2, ans, n);
                path.pop_back();
                visity[j] = false;
                visit1[depth + j] = false;
                visit2[depth - j + n - 1] = false;
            }
        }
        vector<vector<string>> solveNQueens(int n) {
            vector<bool> visity(n, false);
            vector<bool> visit1(2 * n, false);
            vector<bool> visit2(2 * n, false);
            vector<vector<string>> ans;
            vector<long long int> path;
            backtrack(0, path, visity, visit1, visit2, ans, n);
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.