[Leetcode] N-Queens
8197 단어 LeetCode
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where
'Q'
and '.'
both indicate a queen and an empty space respectively. For example,There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
소급법, DFS, 할 말이 없어요.
1 class Solution {
2 public:
3 bool isValid(vector<string> &board, int x, int y) {
4 for (int i = 0; i < x; ++i) {
5 if (board[i][y] == 'Q') return false;
6 }
7 for (int i = 0; i < board.size(); ++i) {
8 for (int j = 0; j < board.size(); ++j) {
9 if (i != x && j != y && i-j == x-y && board[i][j] == 'Q')
10 return false;
11 if (i != x && j != y && i+j == x+y && board[i][j] == 'Q')
12 return false;
13 }
14 }
15 return true;
16 }
17
18 void solveHelper(vector<vector<string> > &res, vector<string> &board, int idx) {
19 if (idx == board.size()) {
20 res.push_back(board);
21 return;
22 }
23 for (int i = 0; i < board.size(); ++i) {
24 board[idx][i] = 'Q';
25 if (isValid(board, idx, i)) {
26 solveHelper(res, board, idx + 1);
27 }
28 board[idx][i] = '.';
29 }
30 }
31
32 vector<vector<string> > solveNQueens(int n) {
33 vector<vector<string> > res;
34 vector<string> board;
35 string row;
36 for (int i = 0; i < n; ++i) {
37 row.push_back('.');
38 }
39 for (int i = 0; i < n; ++i) {
40 board.push_back(row);
41 }
42 solveHelper(res, board, 0);
43 return res;
44 }
45 };
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.