solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

typedef pair<int, int> pii;
class Solution {
   public:
    vector<vector<string>> solveNQueens(int n) {

        vector<pii> have;

        vector<vector<string>> ans;

        string s = "";
        for (int i = 0; i < n; i++) s += '.';
 
        
        auto ok = [&](int x, int y) {
            for (auto it : have) {
                if (it.second == y) return false;
                if (y - x == it.second - it.first) return false;
                if (y + x == it.second + it.first) return false;
            }
            return true;
        };

        function<void(int)> dfs = [&](int dep) {
            if (dep == n) {
                vector<string> tmp;
                for (int i = 0; i < n; i++) {
                    tmp.push_back(s);
                }
                for (auto it : have) {
                    int x = it.first, y = it.second;
                    tmp[x][y] = 'Q';
                }
                ans.push_back(tmp);
                return;
            }

            for (int i = 0; i < n; i++) {
                if (ok(dep, i)) {
                    have.push_back({dep, i});
                    dfs(dep + 1);
                    have.pop_back();
                }
            }
        };
        dfs(0);
        return ans;
    }
};