C++ solution from crack the interview page 332


  • 0
    K
    class Solution {
    public:
    vector<string>convert(vector<int>columns, int n)
    {
        vector<string>solution(n);
        for(int i=0;i<n;i++)solution[i].resize(n,'.');
        for(int i=0; i<n; i++)solution[i][columns[i]] = 'Q';
        
        return solution;
    }
    bool valid(vector<int>columns, int rows, int col)
    {
        for(int prev=0; prev<rows; prev++)
        {
            int queen=columns[prev];
            if(col==queen)return false;
            if(abs(rows-prev) == abs(col-queen))return false;
        }
    
        return true;
    
    }
    
    void helper(int rows, vector<int>&columns, vector<vector<string> >&res, int n)
    {
        int col;
        if(rows==n)res.push_back(convert(columns, n));
        else 
        {
            for(col=0; col<n; col++)
            {
                if(valid(columns, rows, col))
                {
                    columns[rows] = col;
                    helper(rows+1, columns, res, n);
                }
            }   
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>>res;
        vector<int>columns(n);
        helper(0, columns, res, n);
        return res;
    }
    

    };


Log in to reply
 

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