一.题目
题目链接
http://lx.lanqiao.cn/problem.page?gpid=T68
问题描述
给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。
输入格式
输入的第一行为一个整数n,表示棋盘的大小。
接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。
接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。
输出格式
输出一个整数,表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
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
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0
二.解决
算法:搜索思考:每行都要放置黑皇后和白皇后,其实这就是n皇后问题(n*n的棋盘下放置n个皇后,它们之间不同行不同列不同对角线),在n行放置好白皇后的基础上放置黑皇后。
注释:dfs(i,s)--i表示目前放置的行数,s表示皇后的颜色(设s=2,表示当前为白皇后,s=3,表示当前为黑皇后)
思路:
开始先放置白皇后,起始为:dfs(0,2)
当dfs(i,n)中的i=n时,表示前n行已放置,判断当前皇后颜色状态:
若s=2,表示n个白皇后全部放置完毕,开始放置黑皇后,程序执行dfs(0,3);
若s=3,表示n个黑皇后全部放置完毕,又因为白皇后在黑皇后放置之前已放置完毕,所以可知n个黑皇后和n个白皇后都放置完毕,所以sum++;
代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int mp[10][10]; 4 int sum,n; 5 //检测是否符合放置皇后的条件 6 int check(int x,int y,int s){ 7 for(int i=0;i<x;i++){ //测试该列是否放过同种颜色的皇后 8 if(mp[i][y]==s) return 0; 9 } 10 for(int i=x-1,j=y-1;i>=0&&j>=0;i--,j--){ //测试左对角线是否放过同种颜色的皇后 11 if(mp[i][j]==s) return 0; 12 } 13 for(int i=x-1,j=y+1;i>=0&&j<n;i--,j++){ //测试右对角线是否放过同种颜色的皇后 14 if(mp[i][j]==s) return 0; 15 } 16 return 1; 17 } 18 //每层都要放置黑皇后和白皇后 19 void dfs(int x,int s){ 20 if(x==n){//表示放置次数达到n 21 if(s==2) dfs(0,3);//开始去放置黑皇后 22 else sum++;//表示黑皇后与白皇后都放置完毕,方法加一 23 return ; 24 } 25 for(int j=0;j<n;j++){ 26 if(mp[x][j]!=1) continue; 27 if(check(x,j,s)==0) continue; 28 else mp[x][j]=s;//表示该层可以放置皇后 29 dfs(x+1,s);//下一层 30 mp[x][j]=1;//回溯 31 } 32 return ; 33 } 34 35 int main(){ 36 cin>>n; 37 for(int i=0;i<n;i++){ 38 for(int j=0;j<n;j++){ 39 cin>>mp[i][j]; 40 } 41 } 42 sum=0; 43 //设放置白皇后状态s=2; 放置黑皇后s=3 44 dfs(0,2);//先在n行棋盘放置完白皇后 45 cout<<sum<<endl; 46 }
注意点(写过的错误):
1.判断左对角线是否存在同颜色皇后时:for(int i=0,j=0;i<n,j<n;i++,j++) 这判断的是(0,0)到(n-1,n-1)这一条线,但我真正要判断的是(x,y)的左对角线,这条对角线不一定是(0,0)到(n-1,n-1)的这条线,所以check语句错误,正确的是for(int i=x-1,j=y-1;i>=0&&j>=0;i--,j--)
2.同理,判断右对角线是否存在同颜色皇后时,也是类似错误
3.不要忘记dfs里面的return 语句,停止执行下面的语句。