【HPUoj】1218 - 2n皇后问题（dfs）

FishWang

发布于 2025-08-27 12:26:20

10000

代码可运行

运行总次数：0

代码可运行

题目链接：点击打开题目

1218: 2n皇后问题 [搜索] 时间限制: 1 Sec 内存限制: 128 MB

提交: 25 解决: 9 统计题目描述给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。

现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。

问总共有多少种放法？

输入输入的第一行为一个整数n，表示棋盘的大小。

接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

n小于等于8。

输出输出一个整数，表示总共有多少种放法。

样例输入 4 1111 1111 1111 1111 4 1011 1111 1111 1111 样例输出 2 0 来源蓝桥杯

直接对黑白处理，搜索就行了。数据比较小。

import java.util.Scanner;

class Queen
{
    public boolean[][] black = new boolean[15][15];
    public boolean[][] white = new boolean[15][15];
    public int l;
    public String[] mapp = new String[15];
    public int ans;

    public void init(int n)
    {
        this.l = n;
        ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
                black[i][j] = white[i][j] = false;
        }
    }

    public Queen(int n)
    {
        init(n);
    }

}

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n;
        while (sc.hasNext())
        {
            n = sc.nextInt();
            Queen q = new Queen(n);
            for (int i = 0 ; i < n ; i++)
            {
                q.mapp[i] = sc.next();
            }
            solve(q);
        }
    }

    public static boolean check(Queen q, int x, int y, int color)
    {
        if (q.mapp[x].charAt(y) == '0')
            return false;
        if (color == 1)     //黑色
        {
//          if (q.white[x][y])      //搜索黑色的情况下同行不会有白色先出现
//              return false;
            for (int i = 0 ; i < x ; i++)       //扫描列
            {
                if (q.black[i][y] == true)
                    return false;
            }
            int tx = x,ty = y;
            while (tx >= 0 && tx < q.l && ty >= 0 && ty < q.l)      //主对角线
            {
                if (q.black[tx][ty])
                    return false;
                tx--;
                ty--;
            }
            tx = x;
            ty = y;
            while (tx >= 0 && tx < q.l && ty >= 0 && ty < q.l)      //副对角线
            {
                if (q.black[tx][ty])
                    return false;
                tx--;
                ty++;
            }
        }
        else
        {
            if (q.black[x][y])
                return false;
            for (int i = 0 ; i < x ; i++)       //扫描列
            {
                if (q.white[i][y] == true)
                    return false;
            }
            int tx = x,ty = y;
            while (tx >= 0 && tx < q.l && ty >= 0 && ty < q.l)      //主对角线
            {
                if (q.white[tx][ty])
                    return false;
                tx--;
                ty--;
            }
            tx = x;
            ty = y;
            while (tx >= 0 && tx < q.l && ty >= 0 && ty < q.l)      //副对角线
            {
                if (q.white[tx][ty])
                    return false;
                tx--;
                ty++;
            }
        }
        return true;
    }

    public static void solve(Queen q)
    {
        dfs(q,0);
        System.out.println(q.ans);
    }

    public static void dfs(Queen q, int l)
    {
        if (l == q.l)
        {
            q.ans++;
            return;
        }
        for (int i = 0 ; i < q.l ; i++)
        {
            if (check(q,l,i,1))
            {
                q.black[l][i] = true;
                for (int j = 0 ; j < q.l ; j++)
                {
                    if (check(q,l,j,2))
                    {
                        q.white[l][j] = true;
                        dfs(q,l+1);
                        q.white[l][j] = false;
                    }
                }
                q.black[l][i] = false;
            }
        }
    }
}

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

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

return