编程趣味挑战：用c++、java、go三种版本实现2024年高考数学填空压轴题！_高考编程例题

从高中毕业已经两年的大学牲昨天好奇的看了下今年的高考数学题，其中有一道填空题挺有意思的，废话不多说直接看题！

题目：

分析：

本题实际上是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: