蓝桥杯训练 2n皇后
2024-08-31 17:32:42
问题描述
给定一个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
import java.util.*; public class Test__23 {
static int m;
static int count = 0;
static int H[][];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
H = new int[m][m];
for(int i=0; i<H.length; i++){
for(int j=0; j<H[i].length; j++){
H[i][j] = sc.nextInt();
}
}
Put(0,2);
System.out.println(count);
} public static void Put(int t,int s)
{
if(t==m)
{
if(s==2)Put(0,3);
else count++;
return ;
}
for(int i=0;i<m;i++)
{ if(H[t][i]!=1)continue;
if(place(t,i,s))H[t][i]=s;
else continue;
Put(t+1,s);
H[t][i]=1; //回溯法的关键
}
return ;
} public static boolean place(int t,int i,int s) //检查同一列是否有相同的
{
for(int q=t-1;q>=0;q--)
{
if(H[q][i]==s)return false;
}
for(int q=t-1,w=i-1;q>=0&&w>=0;q--,w--) //检查主对角线 这行以下的还没放 不检查
{
if(H[q][w]==s)return false;
}
for(int q=t-1,w=i+1;q>=0&&w<=m-1;q--,w++) //检查另一个对角线
{
if(H[q][w]==s)return false;
}
return true;
}
}
最新文章
- 【Linux】Vim语法高亮显示
- mysql索引失效
- NXOPEN环境配置
- android 混淆导致友盟反馈出错
- 20145301&;20145321&;20145335实验四
- Oracle RMAN 备份一例
- 泛函编程(37)-泛函Stream IO:通用的IO处理过程-Free Process
- C#下搭建文件格式转换服务器
- github实践操作
- 【HDOJ】3473 Minimum Sum
- java多线程之停止线程
- 通过开发工具发布web应用到tomcat服务器中--对于小白,大神可以忽略不看,勿喷,谢谢
- twisted学习笔记4 部署Twisted 应用程序
- iOS Learning
- 关于easyUI的datebox加失去焦点事件即click、blur等
- 如何创建Filter的属性页
- 在Hadoop集群上的HBase配置
- .Net Core DES加密解密
- Ubuntu下从外网上北邮人BT
- Python安装常见问题(1):zipimport.ZipImportError: can&#39;t decompress data