问题描述 给定一个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
用的回溯法，建立了三个二维数组，一个存放不允许摆放棋子位置的数据，两个存放黑皇后和白皇后。我的写法是先搜索黑皇后的摆放方案，在最里面嵌套搜索白皇后摆放方案。写的时候要注意最里面嵌套的白皇后搜索中白皇后的行数 需要在每次进入while循环前进行初始化。 网上很多解决方案都比用三个二维数组的次方案简洁，此方案要繁琐不少。 开始的时候三个数组是8*8的，然而每到7*7以及以上的数据时都会出错，数组有越界的地方，故改成了三个9*9的数组
#include<iostream>using namespace std;bool judeg(int a[9][9],int c[9][9],int k,int t,int n){//黑皇后的放置判断 if(c[k][t]==0) return false; for(int i=0;i<k;i++){ for(int j=0;j<n;j++){ if(a[i][j]==1){ if(j==t||i-k==t-j||i-k==j-t) return false; } } } return true;}bool judeg(int a[9][9],int c[9][9],int b[9][9],int k,int t,int n){//白皇后的放置判断，判断中加入了黑皇后的位置 if(b[k][t]==1||c[k][t]==0) return false; for(int i=0;i<k;i++){ for(int j=0;j<n;j++){ if(a[i][j]==1){ if(j==t||i-k==t-j||i-k==j-t) return false; } } } return true;}int main(){ int a[9][9]={0};//黑皇后 int b[9][9]={0};//白皇后 int c[9][9]={0};//不能摆放棋子的位置用0表示 int k=0,j=0,m=0,n=0,u=0,count=0; cin>>u; for(int i=0;i<u;i++){ for(int p=0;p<u;p++){ cin>>c[i][p]; } } while(k>=0){//先回溯黑皇后 for(int y=0;y<u;y++)//将棋子位置向前移动一位 if(a[k][y]==1){ a[k][y] = 0; j=y+1; } while(k<u&&!judeg(a,c,k,j,u)){//进行判断 j++; if(j==u) break; } if(k<u){//放置棋子 a[k][j] = 1; } if(j<u){ if(k==u-1){//完成一次摆放方案后对白皇后的摆放进行回溯 m=0;//初始化白皇后的行数 while(m>=0){ for(int y=0;y<u;y++) if(b[m][y]==1){ b[m][y] = 0; n=y+1; } while(m<u&&!judeg(b,c,a,m,n,u)){ n++; if(n==u) break; } if(m<u){ b[m][n] = 1; } if(n<u){ if(m==u-1){ count++; }else{ n = 0; m++; } }else{ b[m][n] = 0; n = 0; m--; } } }else{//黑皇后进行下一行的摆放 j = 0; k++; } }else{//此方案不可行会退到上一行 a[k][j] = 0; j = 0; k--; } } cout<<count; return 0;}新闻热点
疑难解答
