33. N-Queens

//超时了，花了1个小时吧。最后一个bug查了好久。

class Solution { public: /* * @param n: The number of queens * @return: All distinct solutions */ bool checkValid(vector<int> pre, int cur){ for(int i = 0; i < pre.size(); i++){ if(pre[i] == cur || pre[i] == cur - (pre.size() - i) || pre[i] == cur + (pre.size() - i)){ return false; } } return true; } void dfs(int n, int rowCnt, vector<vector<int>> &res, vector<int> &resElem){ if(rowCnt == n){ res.push_back(resElem); return; } for(int i = 0; i < n; i++){ //resElem.push_back(i); 这里不能这样写啊，只有判断valid了，才能放入啊，脑残了！ //以后，记住，无论什么题目，先判断valid，再加element。 if(checkValid(resElem, i)){ resElem.push_back(i); dfs(n, rowCnt + 1, res, resElem); resElem.pop_back(); } // resElem.pop_back(); } return; } vector<vector<string>> solveNQueens(int n) { // write your code here // DFS vector<string> resElem; vector<vector<string>> res; if(n == 1){ resElem.push_back("Q"); res.push_back(resElem); return res; } if(n <= 3){ //res.push_back(resElem); return res; } vector<int> resElem1; vector<vector<int>> res1; dfs(n, 0, res1, resElem1); for(int i = 0; i < res1.size(); i++){ res.push_back(convert(res1[i])); } return res; } vector<string> convert(vector<int> &a){ const int n = a.size(); vector<string> res(n); string row = ""; for(int i = 0; i < n; i++){ row += '.'; } for(int i = 0; i < n; i++){ res[i] = row; res[i][a[i]] = 'Q'; } return res; } };