当前位置: 代码迷 >> 综合 >> Leetcode每日一题:52.N-Queens II(N皇后Ⅱ)
  详细解决方案

Leetcode每日一题:52.N-Queens II(N皇后Ⅱ)

热度:69   发布时间:2024-03-06 03:28:53.0

在这里插入图片描述
思路:一共有n行n列,放置n个皇后,同行同列同斜对角线都最多只能有一个皇后;相当于从0~n-1行,每一行放一个,把第k行的皇后放在第j列时,检查前面0~k-1行的皇后是否与第k行皇后的位置冲突,若冲突则尝试把它放下一列
在这里插入图片描述

//判断第k行的皇后所放置的位置是否与前面k-1个皇后冲突
bool judge(int *place, int k, int j)
{
    for (int i = 0; i < k; i++){
    //判断第i个皇后是否与第k个皇后同列,或者同对角线abs(x2-x1)==abs(y2-y1)if (place[i] == j || (k - i) == abs(j - place[i])) //如果冲突{
    return true;}}return false;
}//放置第k行的皇后到place[k]列上void check(int *place, int k, int n, int &res){
    if (k == n) //已放置n个皇后,无需再放置,方案个数++{
    res++;return;}for (int j = 0; j < n; j++) //第k行的皇后所放置的位置从0~n-1挨个试{
    if (!judge(place, k, j)) //如果第k行的皇后放在第j列与前面的皇后不冲突的话,开始放置第k+1个皇后{
    place[k]=j;check(place, k + 1, n, res);}//如果冲突,则尝试下一个位置}}int totalNQueens(int n)
{
    int res = 0;int *place = new int[n];check(place, 0, n, res);//初始放置第0行的皇后return res;
}