题解 | #N皇后问题#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型 the n
 * @return int整型
 */
#include <string.h>
void func(char** grid, int order, int rowIndex, int colIndex, int* res) {
    if (order - 1 == rowIndex) {//成功进入最后一行
        *res = *res + 1;
        return;
    }
    char matrix[order][order];//新建数组，递归不改变初始数组
    memcpy(matrix, grid, order * order);
    int i, j;
    for (j = 0; j < order; ++j)//同行清零
        matrix[rowIndex][j] = 0;
    for (i = rowIndex + 1; i < order; ++i)//同列清零
        matrix[i][colIndex] = 0;
    for (i = rowIndex + 1, j = colIndex + 1; i < order && j < order; ++i, ++j)//主对角线清零
        matrix[i][j] = 0;
    for (i = rowIndex + 1, j = colIndex - 1; i < order && j >= 0; ++i, --j)//副对角线清零
        matrix[i][j] = 0;
    for (i = rowIndex + 1, j = 0; i < order && j < order; ++j) {//找到下一行的位置
        if (matrix[i][j])
            func(matrix, order, i, j, res);
    }
}

int Nqueen(int n ) {
    // write code here
    int res = 0;
    char matrix[n][n];
    memset(matrix, 1, n * n);//初始赋值1
    for (int i = 0; i < n / 2; ++i) {//对称性
        func(matrix, n, 0, i, &res);
    }
    res *= 2;
    if (n % 2) func(matrix, n, 0, n / 2, &res);//奇数阶数单独算中间的位置
    return res;
}