试题基础练习 2n皇后问题

GeekLiHua

发布于 2025-01-21 14:18:15

1330

文章被收录于专栏：JavaJava

试题基础练习 2n皇后问题

资源限制内存限制：512.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s 问题描述　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。输入格式　　输入的第一行为一个整数n，表示棋盘的大小。　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。输出格式　　输出一个整数，表示总共有多少种放法。样例输入 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 样例输出 2 样例输入 4 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 样例输出 0 运行结果：

#pragma warning (disable:4996)
#include<bits/stdc++.h>
using namespace std;
const int N = 20;

int n, cnt;
int g[N][N];
bool col[N], dg[N], udg[N];
bool col2[N], dg2[N], udg2[N];

void dfs2(int u);
void dfs(int u)
{
    if (u == n)
    {
        dfs2(0); return;
    }
    for (int i = 0; i < n; ++i)
    {
        if (!col[i] && !dg[u + i] && !udg[n - u + i] && g[u][i] == 1)
        {
            g[u][i] = 0;
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = 1;
        }
    }
}
void dfs2(int u)
{
    if (u == n)
    {
        cnt++; return;
    }
    for (int i = 0; i < n; ++i)
    {
        if (!col2[i] && !dg2[u + i] && !udg2[n - u + i] && g[u][i] == 1)
        {
            g[u][i] = 0;
            col2[i] = dg2[u + i] = udg2[n - u + i] = true;
            dfs2(u + 1);
            col2[i] = dg2[u + i] = udg2[n - u + i] = false;
            g[u][i] = 1;
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            scanf("%d", &g[i][j]);
        }
    }
    dfs(0);
    printf("%d\n", cnt);
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-05，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs