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

样例输出

import java.util.Scanner;     //0表示不可放皇后，1可放皇后，2表示已放黑皇后，3表示已放白棋 
public class Main {
static int sum=0,black=2,white=3;
static boolean judge_Queen(int i,int j,int k,int n,int Queen[][]){
int r,c;          //表示行和列
//从8个方向判断是否可以放皇后
for(r=0;r<n;r++)       //上下
if(Queen[r][j]==k)
return false;
for(c=0;c<n;c++)       //左右
if(Queen[i][c]==k)
return false;
for(r=i-1,c=j-1;r>=0&&c>=0;r--,c--)   //左上角
if(Queen[r][c]==k)
return false;
for(r=i+1,c=j+1;r<n&&c<n;r++,c++)     //右下角
if(Queen[r][c]==k)
return false;
for(r=i-1,c=j+1;r>=0&&c<n;r--,c++)     //右上角
if(Queen[r][c]==k)
return false;
for(r=i+1,c=j-1;r<n&&c>=0;r++,c--)     //左下角
if(Queen[r][c]==k)
return false;

return true;
    }
static void dls(int i,int t,int n,int Queen[][]){  //先找黑皇后，再找白皇后
int j;
if(i>=n){
if(t==0){    //黑白皇后都找到了
                sum++;
                t=1;
return;
            }
            t=0;   //只找到黑皇后，继续找白皇后
            i=0;
        }
if(t!=0){      //寻找是否满足黑皇后 
for(j=0;j<n;j++)
if(judge_Queen(i,j,black,n,Queen)&&Queen[i][j]==1){

                    Queen[i][j]=black;
                    dls(i+1,t,n,Queen);
                    Queen[i][j]=1;
                }
        }
else{       //判断是否满足白皇后
for(j=0;j<n;j++){
if(judge_Queen(i,j,white,n,Queen)&&Queen[i][j]==1){
                    Queen[i][j]=white;
                    dls(i+1,t,n,Queen);
                    Queen[i][j]=1;
                }

            }

        }

    }

public static void main(String[] args) {
// TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
int i,j;
int n=sc.nextInt();
int Queen[][]=new int [n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
                Queen[i][j]=sc.nextInt();
        dls(0,1,n,Queen);
        System.out.println(sum);


    }

}

秒客网

基础练习 2n皇后问题

相关文章