python/TangDou/Dfs/DFS13.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 110;
int n, m, Max;
int b1[N]; //正对角线
int b2[N]; //反对角线
//就是加一个常数增量，将x-y与y-x转化为正数，当然大于10的数字也可以，但对应的数组长度要装的下才行。
const int M = 30;

void dfs(int x, int y, int sum) {
    if (x == n + 1) {
        //收集最大值
        Max = max(Max, sum);
        return;
    }
    //如果这个位置可以放，那么我们可以选择放
    if (!b1[x + y] && !b2[x - y + M]) {
        b1[x + y] = 1, b2[x - y + M] = 1;

        if (y == m)
            dfs(x + 1, 1, sum + 1);
        else
            dfs(x, y + 1, sum + 1);

        b1[x + y] = 0, b2[x - y + M] = 0;
    }
    //不管可以不可以放，都可以选择不放
    if (y == m)dfs(x + 1, 1, sum);
    else dfs(x, y + 1, sum);
}

int main() {
    cin >> n >> m; // n行m列
    dfs(1, 1, 0);  //从(1,1)位置出发,0:表示已经安排好的传教士数量
    cout << Max << endl;
    return 0;
}