38 lines
1.0 KiB
C++
38 lines
1.0 KiB
C++
#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;
|
||
} |