[leetcode题解]52. N-Queens II

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

N皇后问题,跟51题是一样的,只不过51题要求把所有的放置方法输出来,本题只要求输出放置方案的个数,所以代码可以直接使用上题代码,只需要把返回放置方案的部分去掉即可。

总的方法见上篇文章N-queues详细分析

C语言代码:

#include <stdbool.h>

#define N 100
#define MAX 120000
#define ND 3
int dirs[ND][2] = { {-1, 0}, {-1, -1}, {-1, 1} };

bool used[N][N];

bool check_dir(int x, int y, int dx, int dy, int n) {
    int nx, ny;
    bool ret = true;

    for (;;) {
        nx = x + dx;
        ny = y + dy;

        if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
            break;
        }

        if (used[nx][ny]) {
            ret = false;
            break;
        }

        x = nx;
        y = ny;
    }

    return ret;
}

bool check(int x, int y, int n) {
    int i;
    bool ret = true;

    for (i = 0; i < ND; i++) {
        ret = check_dir(x, y, dirs[i][0], dirs[i][1], n);
        if (!ret) {
            return ret;
        }
    }
    return ret;
}

void dfs(int idx, int n, int *sol_cnt) {
    int i, j;
    char **arr = NULL;

    if (idx >= n) {
        *sol_cnt += 1;
        return;
    }

    for (i = 0; i < n; i++) {
        if (!check(idx, i, n)) {
            continue;
        }

        used[idx][i] = true;
        dfs(idx + 1, n, sol_cnt);
        used[idx][i] = false;
    }
}

int totalNQueens(int n){
    int res = 0;
    
    dfs(0, n, &res);
    return res;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]52. N-Queens II

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/218.html

相关文章