暴力深搜
class Solution { public: vector<vector<string>> ans; vector<string> tmp; bool vis[1005][1005] = {}, row[1005] = {}; void dfs(int col, int &n) { if (col == n) { ans.push_back(tmp); return; } for (int i = 0; i < n; ++i) if (!row[i] && !vis[i][col]) { vector<pair<int, int>> tt; row[i] = 1; int k = 1; while (col + k < n && i + k < n) { if (!vis[i + k][col + k]) tt.push_back(make_pair(i + k, col + k)); ++k; } k = 1; while (col + k <n && i - k >= 0) { if (!vis[i - k][col + k]) tt.push_back(make_pair(i - k, col + k)); ++k; } for (auto &x : tt) vis[x.first][x.second] = 1; tmp[i][col] = 'Q'; dfs(col + 1, n); tmp[i][col] = '.'; for (auto &x : tt) vis[x.first][x.second] = 0; row[i] = 0; } } vector<vector<string>> solveNQueens(int n) { tmp.assign(n, string(n, '.')); dfs(0, n); return ans; } };