9ms one-pass C++ code.


  • 0
    M

    Idea is pretty much same as those in the discuss area. A little difference is I didn't use two-dimensional array to mark the place of Queen. Instea, one-dimension is good enough for this problem.

    class Solution {
    public:
        bool inDeathZone(int j, int inspectedRow, vector<int>& haveQueen) {
            for (int i = 0; i < inspectedRow; i++) {
                int deathPos = haveQueen[i], diff = inspectedRow-i;
                if (j == deathPos || j == deathPos + diff || j == deathPos - diff) {
                    return true;
                }
            }
            return false;
        }
        void loadResult(vector<string>& tempResult, vector<vector<string>>& result, 
        int currentRow,  vector<int>& haveQueen, int n) {
            if (currentRow == n) {
                result.push_back(tempResult);
            }
            else {
                string rowString = string(n,'.');
                for (int i = 0; i < rowString.length(); i++) {
                    if (!inDeathZone(i, currentRow, haveQueen)) {
                        rowString[i] = 'Q';
                        haveQueen[currentRow] = i;
                        tempResult.push_back(rowString);
                        loadResult(tempResult, result, currentRow+1, haveQueen, n);
                        rowString[i] = '.';
                        tempResult.pop_back();
                    }
                }
            }
        }
        vector<vector<string>> solveNQueens(int n) {
            vector<int> haveQueen(n);
            vector<vector<string>> result;
            vector<string> tempResult;
            loadResult(tempResult, result, 0, haveQueen, n);
            return result;
        }
    };
    

Log in to reply
 

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