蓝桥杯 basic27试题基础练习 2n皇后问题

Ora ·

更新时间:2024-09-21

· 766 次阅读

记录我的刷题历程

蓝桥杯 basic27试题基础练习 2n皇后问题 资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

给定一个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

样例输出

样例输入

4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

思路与大致想法

刚开始
想到的是用另外一个数组存储原数组状态，已知两两之间不可在同行，同列，同对角线，又需要放置n个皇后，因此循环的次数就是n次，每行每列都会有一个，但是落实到具体就不会了
然后得知该类问题有一个共同的解法就是bfs和dfs，为此特地去学了这两个算法，有了新的理解
N是一共有几步
dfs（int n）//n代表当前层数
{
if(结束条件){
表示所有步骤走完，正确结果还是得自己删选
}
for(i:N){
if( 约束条件){
dfs(n+1)//表示进入下一步
（a[i]=0）//如果需要回溯的话，寻找多个解法就需要添加
}
}
}
相当于主干部分吧，
因此有了以下思考，2n皇后可拆分成两个步骤，第一个步骤就是先寻找白皇后，表示为2，找完一次结果之后，进入黑皇后的寻找，然后就会有新的条件限制，因此我的代码涉及两个dfs的搜寻。

正确代码部分


import java.util.Scanner;
public class Main {
    static Scanner scanner = new Scanner(System.in);
    static int n = scanner.nextInt();
    static int count=0;
    public static void main(String[] args) {
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = scanner.nextInt();
            }
        }
        dfs(a,0);
        System.out.println(count);
    }
    public static void dfs(int[][] a,int N){
        if(N==n){
            int flag=0;
            for (int i=0;i<n;i++){
                for (int j=0;j<n;j++){
                    if(a[i][j]==2){
                        flag++;
                    }
                }
                if(flag!=1){
                    return;
                }
                else {
                    flag=0;
                }
            }
            dfs2(a,0);
            return;
        }
        for (int i=0;i<n;i++){
            if(check(a,N,i)){
                a[N][i]=2;
                dfs(a,N+1);
                a[N][i]=1;
            }
        }
    }
    public static void dfs2(int[][] a,int N){
        if(n==N){
            int flag=0;
            for (int i=0;i<n;i++){
                for (int j=0;j<n;j++){
                    if(a[i][j]==3){
                        flag++;
                    }
                }
                if(flag!=1){
                    return;
                }
                else {
                    flag=0;
                }
            }
            count++;
            return;
        }
        for (int i=0;i<n;i++){
            if(check2(a,N,i)){
                a[N][i]=3;
                dfs2(a, N+1);
                a[N][i]=1;
            }
        }
    }
    public static boolean check(int[][] a,int N,int p){
        if(a[N][p]==0) return false;
        for (int j=0;j<N;j++) {
            for (int i = 0; i < n; i++) {
                if(a[j][i]==2){
                    if(i==p||Math.abs(N-j)==Math.abs(i-p)){
                        return false;
                    }
                }
            }
        }
        return true;
    }
    public static boolean check2(int[][] a,int N,int p){
        if(a[N][p]==0||a[N][p]==2) return false;
        for (int j=0;j<N;j++) {
            for (int i = 0; i < n; i++) {
                    if(a[j][i]==3) {
                        if (i == p || Math.abs(N - j) == Math.abs(i - p)) {
                            return false;
                        }
                    }
            }
        }
        return true;
    }
}

成功截图

在这里插入图片描述