N 皇后

简介: N 皇后

N 皇后


n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。


给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。


每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。


示例 1:


cb2d6f75be6a92d99667a176a17015eb.jpg


输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。


示例 2:


输入:n = 1
提示:输出:[["Q"]]


提示:


  • 1 <= n <= 9
  • 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。


以下程序实现了这一功能,请你填补空白处的内容:


#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
  vector<vector<string>> solveNQueens(int n)
  {
    vector<vector<string>> res;
    vector<int> stack(n);
    vector<string> solution(n, string(n, '.'));
    dfs(n, 0, stack, solution, res);
    return res;
  }
private:
  void dfs(int n, int row, vector<int> &stack, vector<string> &solution, vector<vector<string>> &res)
  {
    if (row == n)
    {
      res.push_back(solution);
    }
    else
    {
      for (int i = 0; i < n; i++)
      {
        if (row == 0 || !conflict(stack, row, i))
        {
          solution[row][i] = 'Q';
                    stack[row] = i;
                    dfs(n, row + 1, stack, solution, res);
                    solution[row][i] = '.';
        }
      }
    }
  }
  bool conflict(vector<int> &stack, int row, int col)
  {
    for (int i = 0; i < row; i++)
    {
      if (col == stack[i] || abs(row - i) == abs(col - stack[i]))
      {
        return true;
      }
    }
    return false;
  }
}


目录
相关文章
|
6月前
|
机器学习/深度学习 Java
leetcode-51:N 皇后
leetcode-51:N 皇后
429 0
leetcode-51:N 皇后
|
6月前
|
机器学习/深度学习 移动开发 算法
n-皇后问题
n-皇后问题
29 0
|
机器学习/深度学习 算法 安全
LeetCode - #51 N 皇后
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
LeetCode - #51 N 皇后
|
移动开发 算法
DFS深度优先算法 —— AcWing 842. 排列数字AcWing 843. n-皇后问题
DFS深度优先算法 —— AcWing 842. 排列数字AcWing 843. n-皇后问题
102 0
|
机器学习/深度学习 算法 网络协议
算法思想之n-皇后问题
算法思想之n-皇后问题
|
机器学习/深度学习
受伤的皇后(dfs)
受伤的皇后(dfs)
|
机器学习/深度学习
N皇后问题
N皇后问题
76 0
AcWing——方格迷宫(有点不一样的迷宫问题)
AcWing——方格迷宫(有点不一样的迷宫问题)
87 0
|
算法
回溯法——力扣51. N 皇后
回溯法——力扣51. N 皇后
76 1
回溯法——力扣51. N 皇后
|
机器学习/深度学习 算法 JavaScript
从 DFS 到回溯法,再看 N 皇后问题
DFS 是深度搜索,是暴力的,是一条道走到黑的,是一次性搜到底的!那么,搜到底发现没有路了,就得回退去找另外的路,再继续莽着搜!既然要回退,就必须保存走过每个点的所有信息,包括先后顺序;这个回退的过程就叫 回溯。