1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
class { public: std::vector<std::vector<std::string> > solveNQueens(int n) { std::vector<std::vector<std::string> > res; std::vector<std::string> nQueens(n, std::string(n, '.')); solveNQueens(res, nQueens, 0, n); return res; } private: void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row, int &n) { if (row == n) { res.push_back(nQueens); return; } for (int col = 0; col != n; ++col) if (isValid(nQueens, row, col, n)) { nQueens[row][col] = 'Q'; solveNQueens(res, nQueens, row + 1, n); nQueens[row][col] = '.'; } } bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) { for (int i = 0; i != row; ++i) if (nQueens[i][col] == 'Q') return false; for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) if (nQueens[i][j] == 'Q') return false; for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) if (nQueens[i][j] == 'Q') return false; return true; } };
|
近期评论