Java实现蓝桥杯VIP 基础练习 2n皇后问题

基础练习 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

样例输出

2

样例输入

4

1 0 1 1

1 1 1 1

1 1 1 1

1 1 1 1

样例输出

0

package 蓝桥杯VIP;

import java.util.Scanner;

public class 皇后问题 {

	static int sum=0;//统计符合的数目

	public static void main(String[] args)

	{

		Scanner db=new Scanner (System.in);

		int n=db.nextInt();

		int arr[]=new int [n]; //皇后放置位置

		int wee[][]=new int [n][n];// 接受输入时的0 1

		for(int i=0; i<n; i++)

			for(int j=0; j<n; j++)

				wee[i][j]=db.nextInt();

		queen(0, 0, arr, wee);//递归调用

		System.out.println(sum);

	}

	public static int queen(int su, int k, int arr[], int[][] wee)

	//su==0表示落子的是白皇后	为1 表示落子的是黑皇后   k表示第k个皇后

	{

		if(k==arr.length)//如果所有皇后都放置

		{

			if(su==0)//判断放置的是否是白皇后

			{

				arr=new int[arr.length];	//如果白皇后都被放置，初始化黑皇后的位置

				queen(su+1, 0, arr, wee);

			}

			if(su==1)//判断放置的是否是白皇后

				sum++;	//统计2n皇后的放置种数

			return sum;

		}

		for(int i=0; i<arr.length; i++)//判断第k个皇后位置（列数）行数为k

		{

			if(wee[k][i]==0)	//如果当前位置坐标值为零，则不能放置皇后

				continue;

			int j;

			for(j=0; j<k; j++)//前k-1个皇后位置（列数）行数 为j

				if(arr[j]==i||Math.abs(arr[j]-i)==(k-j))//判断皇后之间是否存在同一列，统一对角线冲突

					break;

			if(j==k)//条件成立时表示第k个与之前的没有冲突

			{

				arr[k]=i;	//第k个皇后位置

				wee[k][i]=0; //将此位置即为0 表示不能再这放置皇后

				queen(su, k+1, arr, wee);	//递归调用下一层

				wee[k][i]=1;

			}

		}

		return sum;

	}

}

原文：https://blog.csdn.net/qiaosheng1010/article/details/79678064

巴特西

Java实现蓝桥杯VIP 基础练习 2n皇后问题

最新文章

热门文章

巴特西

Java实现 蓝桥杯VIP 基础练习 2n皇后问题

最新文章

热门文章

Java实现蓝桥杯VIP 基础练习 2n皇后问题