My 8ms C++ solution


  • 0
    class Solution {
    public:
        vector<int> r, c, d, m;
        int size;
        vector<vector<string>> ret;
        vector<string> tmp;
        vector<vector<string> > solveNQueens(int n) {
            size = n;
            r.resize(n, 0);
            c.resize(n, 0);
            d.resize(2*n-1, 0);
            m.resize(2*n-1, 0);
    
            helper(0, 0);
    
            return ret;
    
        }
    
        void helper(int i, int j) {
            if (j == 0) 
                tmp.push_back(string(size,'.'));
    
            if (r[i] || c[j] || d[i+j] || m[i-j + size-1]) {
                if (j==size-1)
                    tmp.pop_back();
                else
                    helper(i, j+1);
            }
            else {
                tmp[i][j]='Q';
                r[i] = c[j] = d[i+j] = m[i-j+size-1] = 1;
                if (i==size-1) {
                    // find one
                    ret.push_back(tmp);
                }
                else {
                    helper(i+1, 0);
                }
                tmp[i][j]='.';
                r[i] = c[j] = d[i+j] = m[i-j+size-1] = 0;
                if (j==size-1) 
                    tmp.pop_back();
                else
                    helper(i, j+1);
            }
        }

Log in to reply
 

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