原题链接:蓝桥杯基础练习VIP-2n皇后问题
解题思路:
【思路一】先在棋盘上放完白皇后,再在有白皇后的棋盘上放黑皇后。 先用dfs一个一个放白皇后,当到达递归边界时,说明白皇后已经放完,可以放黑皇后了,再调用第二个dfs放黑皇后。用二维数组checkboard[n][n]判断能否放皇后。
【思路二】因为两个皇后除了不能占用同一个棋格,互相不产生其他影响,所以先打印单个皇后(即n皇后)的所有棋盘摆放方案,有row个,然后从row个方案中选出两个方案组合在一起,相当于把一个已经放好白皇后的棋盘和一个已经放好黑皇后的棋盘合在一起。用二维数组temp[row][]存储, 二维数组的每一行表示一种方案,共有row种方案,约束条件是选中的两行数据每一列的数字都不能相同。
注意事项:
【思路二】最后要×2,先放白皇后后放黑皇后 和 先放黑皇后后放白皇后
参考代码:
/*-------------------------------思路一------------------------------*/ #include <cstdio> #include <algorithm> using namespace std; const int maxn = 1000; int checkboard[maxn][maxn]; //棋盘 int vis1[3][maxn]; int vis2[3][maxn]; int n, tot = 0; void search2(int cur){ if(n == cur){ tot++; } else{ for(int i = 0; i < n; i++){ if(checkboard[cur][i] == 1){ if(!vis2[0][i] && !vis2[1][cur + i] && !vis2[2][cur - i + n]){ vis2[0][i] = vis2[1][cur + i] = vis2[2][cur - i + n] = 1; search2(cur + 1); vis2[0][i] = vis2[1][cur + i] = vis2[2][cur - i + n] = 0; } } } } } void print_qipan(){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++) printf("%d ", checkboard[i][j]); printf("\n"); } printf("------------------\n"); } void search(int cur){ if(n == cur){ search2(0); // print_qipan(); // tot++; } else{ for(int i = 0; i < n; i++){ if(checkboard[cur][i] == 1){ if(!vis1[0][i] && !vis1[1][cur + i] && !vis1[2][cur - i + n]){ // C[cur] = i; //打印棋盘时用到 vis1[0][i] = vis1[1][cur + i] = vis1[2][cur - i + n] = 1; checkboard[cur][i] = 0; search(cur + 1); checkboard[cur][i] = 1; vis1[0][i] = vis1[1][cur + i] = vis1[2][cur - i + n] = 0; } } } } } int main (void){ scanf("%d", &n); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ scanf("%d", &checkboard[i][j]); } } search(0); printf("%d",tot); return 0; } /*-------------------------------思路二------------------------------*/ #include <cstdio> #include <algorithm> using namespace std; const int maxn = 1000; int checkboard[maxn][maxn]; //棋盘 int vis[3][maxn]; //判断是否合法 int temp[maxn][maxn], C[maxn]; //temp是将棋盘转换成全排列数字的数组 int n, tot = 0, ting = 0; int row = 0; //temp数组的行数 int *T; void search(int cur){ if(n == cur){ for(int i = 0; i < n; i++){ temp[row][i] = C[i]; } row++; } else{ for(int i = 0; i < n; i++){ if(checkboard[cur][i] == 1){ if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]){ C[cur] = i; vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1; search(cur + 1); vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0; } } } } } int main (void){ scanf("%d", &n); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ scanf("%d", &checkboard[i][j]); } } search(0); for(int i = 0; i < row; i++){ T = temp[i]; for(int j = i + 1; j < row; j++){ int ok = 1; for(int k = 0; k < n; k++){ if(temp[j][k] == T[k]){ ok = 0; break; } } if(ok){ tot++; } } } printf("%d",tot*2); return 0; }
0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复