C++ 3ms


  • 0

    In my opinion, there is only one queen in each column, so I use c [i] = x to denote that in the i row, the queen is in x

    Hope to help you.

    class Solution {
    
        void QueenHelp(int *c, int n, int k, vector<vector<string>>& retVec) {
            if(k == n) {
                vector<string> tmpVec;
                for(int i = 1; i <= n; i++) {
                    string str(n, '.');
                    str[c[i] - 1] = 'Q';
                    tmpVec.push_back(str);
                }
                retVec.push_back(tmpVec);
                return;
            }
    
            for(int i = 1; i <= n; i++) {
               
                bool couldIn = true;
                for(int j = 1; j <= k; j++) {
                    if(i == c[j] 
                        || k+1 - j == i - c[j]
                        || k+1 - j == c[j] - i) {
                        couldIn = false; break;
                    }
                }
                if(couldIn) {
                    c[k+1] = i;
                    QueenHelp(c, n, k+1, retVec);
                }
               
            }
    
        }
      
    public:
        vector<vector<string>> solveNQueens(int n) {
            if(n == 0) return {};
            int *c = new int[n + 1];
    
            vector<vector<string>> retVec;
            for(int i = 1; i <= n; i++) {
                c[1] = i;
                QueenHelp(c, n, 1, retVec);
            }
    
            delete [] c;
            return retVec;
        }
    };
    

Log in to reply
 

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