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

雨点打透心脏的1/2处 2024-04-01 15:07 53阅读 0赞

## 试题 基础练习 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;
    }