友链
姚屹晨

leetcode - [52] N-Queens II

2020/07/23

问题描述

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

给你一个整数n，请计算可以构成N皇后棋盘的总数量。

举个例子：

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.."]
]

解法1

类似题：

[51] N-Queens

思路一样，找到答案时直接ans++即可。

来看下实现：

class Solution {
    
    int ans = 0;
    int N = 40;
    char[][] g = new char[N][N];
    boolean[] col = new boolean[N];
    boolean[] dg  = new boolean[N];
    boolean[] udg = new boolean[N];
    
    private void dfs(int r, int n){
        if (r == n){
            ans++;
            return;
        }
        for (int c = 0; c < n; c++){
            if (!col[c] && !dg[c + r] && !udg[c - r + n]){
                g[r][c] = 'Q';
                col[c] = true;  dg[c + r] = true;  udg[c - r + n] = true;
                dfs(r + 1, n);
                col[c] = false; dg[c + r] = false; udg[c - r + n] = false;
                g[r][c] = '.';
            }
        }
    }
    
    public int totalNQueens(int n) {
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                g[i][j] = '.';
            }
        }
        dfs(0, n);
        return ans;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory