[leetcode] 51. N-Queens (递归）

递归，经典的八皇后问题。

利用一位数组存储棋盘状态，索引表示行，值为-1表示空，否则表示列数。

对行进行搜索，对每一行的不同列数进行判断，如果可以摆放符合规则，则摆放，同时遍历下一行。

遍历过程中，若已经遍历了n行，则保存该状态。

Runtime: 4 ms, faster than 91.35% of C++ online submissions for N-Queens.

class Solution
{public:vector<vector<string>> res;vector<int> queen;int N;vector<vector<string>> solveNQueens(int n){queen = vector<int>(n, -1);N = n;helper(0);return res;}void helper(int pi){if (pi == N){pushit();return;}for (int j = 0; j < N; j++){if (valid(pi, j)){queen[pi] = j;helper(pi + 1);queen[pi] = -1;}}}bool valid(int pi, int pj){for (int i = 0; i <= pi; i++){if (queen[i] == pj || abs(queen[i] - pj) == pi - i)return false;}return true;}void pushit(){vector<string> temp;for (int i = 0; i < N; i++){string str;for (int j = 0; j < N; j++)str.push_back('.');str[queen[i]] = 'Q';temp.push_back(str);}res.push_back(temp);}
};