C++ Non-recursive BFS


  • 0
    A

    My philosophy is NO RECURSIVE, NEVER.
    If you can't write code without using recursive function, you haven't really understood the solution.
    (Why is that over 90% solutions of this problem are recursive??? How come over 70% solutions of all leetcode problems are recursive??? Well, I guess that's because recursive is the easiest.)

    class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<vector<int>> x, y;
            x.push_back(vector<int>(n, -1));
            for (int i = 0; i < n; i++) {
                for (auto xv : x) {
                    for (int k = 0, m; k < n; k++) {
                        for (m = 0; m < i; m++) {
                            if ((xv[m] == k) || (abs(xv[m] - k) == i - m)) break;
                        }
                        if (m >= i) {
                            y.push_back(xv);
                            y.rbegin()->at(i) = k;
                        }
                    }
                }
                x.swap(y);
                y.clear();
            }
            vector<string> b(n, string(n, '.'));
            vector<vector<string>> o;
            for (auto xv : x) {
                o.push_back(b);
                for (uint i = 0; i < n; i++) {
                    (o.rbegin()->at(xv[i]))[i] = 'Q';
                }
            }
            return o;
        }
    };
    

Log in to reply
 

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