一、题意

有若干组数据。
每组数据给一个8*8棋盘，棋盘上每个位置上有一个数字，要求你找出一个八皇后摆法，使得八皇后位置上的数字之和最大。输出这个最大值。

二、解析

经典的八皇后问题，做了一些小修改。但其实还是八皇后问题。
枚举出所有摆法然后维护出最大值即可。

三、代码

#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;
const int n = 8;
int k, a[n + 5][n + 5], ans, vis[3][n * 2 + 5];

void solve(int cur, int sum) {
    if(cur == n) {
        ans = max(ans, sum);
        return;
    }
    for(int i = 0; i < n; i ++) if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]) {
        vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
        solve(cur + 1, sum + a[cur][i]);
        vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
    }
}

int main() {
    cin >> k;
    while(k --) {
        ans = 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) cin >> a[i][j];
        solve(0, 0);
        cout << setw(5) << ans << endl;
    }
}

四、归纳

  • 八皇后问题：按行递归，然后在每行中枚举列，通过vis维护棋盘上每列和每个斜是否已经被占用（行就不用了，因为是按行递归的）。注意递归结束后要回溯，这样才能继续找下一个解。
  • 实际上八皇后问题还教了一种思考方式，就是：我想要确认某个条件时，自己去确认是比较费时的（遍历自己的行、列、斜是否冲突），但是找别人专门管这件事，然后直接去问他是最快的（vis数组专门维护占用情况）。工程上的模块化思想有点像这个，虽然没啥关系就是了...
  • 注意题目有输出格式，这个时候就要靠 iomanip 这个库了，setw(5)表示占位长度，还可以setfill('')表示用''占空位，还有fixed<<setprecision(n)表示保留n位小数等。这些是比较常用的。