从高中毕业已经两年的大学牲昨天好奇的看了下今年的高考数学题，其中有一道填空题挺有意思的，废话不多说直接看题！
题目：
分析：
本题实际上是n-皇后算法题的变形，让我们来回顾一下n-皇后这道题：
n−皇后问题是指将 n 个皇后放在 n×n的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现给定阶数n，求出所有的满足条件的棋子摆法。
本题的不同之处在于只需满足每行每列有且仅有一个皇后即可。
核心思路：深度优先遍历（DFS）& 每行只有一个方格被选中 & 回溯
- 函数 void dfs(int r) : 表示从第r行开始选方格
-
递归结束判定：当 r > n 时说明已经处理完最后一行了，即一种方案，此时cnt ++。
-
枚举第 r 行第 i 列：当第 r 行第 i 列没有被选中时，说明可以选，标记 (r , i)、cor(i)为true；然后递归处理第 r + 1 行，还原状态。
-
计算最大值：当一种方案出现时，该方案中所有的格子，若某个格子被标记为true，则 sum += 第 (i , j) 格子的数值，最终结果取每种方案的最大值即可。
代码：
C++版本：
#include <iostream> using namespace std; const int N = 100; int q[N][N]; int cor[N]; int n,cnt,sum,rel; bool flag[N][N]; void dfs(int r){ if (r > n) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (flag[i][j]) sum+=q[i][j]; } cnt++; rel = max(rel,sum); sum = 0; return; } for(int i = 1; i <= n; i++) { if(!cor[i]) { flag[r][i] = true; cor[i] = 1; dfs(r + 1); cor[i] = 0; flag[r][i] = false; } } } int main() { cin >> n; for(int i = 1;i <= n;i++) for (int j = 1; j <= n; j++) cin >> q[i][j]; dfs(1); cout << "第一空：" << cnt << endl; cout << "第二空: " << rel << endl; return 0; } JAVA版本：
import java.util.Scanner; public class Nqueen { static final int N = 100; static int[][] q = new int[N][N]; static int[] cor = new int[N]; static boolean[][] flag = new boolean[N][N]; static int n, cnt, sum, rel; static void dfs(int r) { if (r > n) { sum = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (flag[i][j]) { sum += q[i][j]; } } } cnt++; rel = Math.max(rel, sum); return; } for (int i = 1; i <= n; i++) { if (cor[i] == 0) { flag[r][i] = true; cor[i] = 1; dfs(r + 1); cor[i] = 0; flag[r][i] = false; } } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { q[i][j] = scanner.nextInt(); } } dfs(1); System.out.println("第一空：" + cnt); System.out.println("第二空: " + rel); } } GO版本：
package main import "fmt" const N = 100 var ( q [N][N]int cor [N]int flag [N][N]bool n, cnt, sum, rel int ) func dfs(r int) { if r > n { sum = 0 for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { if flag[i][j] { sum += q[i][j] } } } cnt++ if sum > rel { rel = sum } return } for i := 1; i <= n; i++ { if cor[i] == 0 { flag[r][i] = true cor[i] = 1 dfs(r + 1) cor[i] = 0 flag[r][i] = false } } } func main() { fmt.Scan(&n) for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { fmt.Scan(&q[i][j]) } } dfs(1) fmt.Println("第一空：", cnt) fmt.Println("第二空: ", rel) } 输出结果：
c++:
java:
go:
原文链接：https://blog.csdn.net/m0_74073836/article/details/139719623?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171949575216800227461536%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=171949575216800227461536&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~times_rank-3-139719623-null-null.nonecase&utm_term=2024%E9%AB%98%E8%80%83
