本文主要是介绍[leetcode]N-Queens,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
64ms过大集合
class Solution {vector<vector<string>> result;
public:bool canPlace(int i, int j, vector<string> &tmp, int n){if(i == 0) return true;for(int k = 0; k < i; k++){if(tmp[k][j] == 'Q') return false;}for(int p = 0; p < i; p++){for(int q = 0; q < n; q++){if((p-q == i-j || p+q == i+j) && tmp[p][q] == 'Q'){return false;}}}return true;}vector<int> possiblePlaces(int i, vector<string> &tmp, int n){vector<int> places;for(int j = 0; j < n; j++){if(canPlace(i,j,tmp, n)){places.push_back(j);}}return places;}void dfs(int level, vector<string> &tmp, int n){if(level >= n){result.push_back(tmp);return;}vector<int> places = possiblePlaces(level, tmp, n);int j;for(int k = 0; k < places.size(); k++){j = places[k];tmp[level][j] = 'Q';dfs(level + 1, tmp, n);tmp[level][j] = '.';}}vector<vector<string> > solveNQueens(int n) {// Start typing your C/C++ solution below// DO NOT write int main() functionresult. clear();vector<string> tmp(n, string(n, '.'));dfs(0, tmp, n);return result;}
};
这篇关于[leetcode]N-Queens的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!