国际象棋
众所周知，“八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。
已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹未尽。作为一个国际象棋迷，他想研究在 $N \times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。
由于方案数可能很大，只需计算答案除以 $1000000007$ (即 $10^9 + 7$) 的余数。
如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字，位于 $(x, y)$ 格的马（第 $x$ 行第 $y$ 列）可以攻击 $(x + 1, y + 2)$、$(x + 1, y − 2)$、$(x − 1, y + 2)$、$(x − 1, y − 2)$、$(x + 2, y + 1)$、$(x + 2, y − 1)$、$(x − 2, y + 1)$ 和 $(x − 2, y − 1)$ 共 $8$ 个格子。
输入格式
输入一行包含三个正整数 $N, M, K$，分别表示棋盘的行数、列数和马的个数。
输出格式
输出一个整数，表示摆放的方案数除以 $1000000007$ (即 $10^9 + 7$) 的余数。
数据范围
对于 $5%$ 的评测用例，$K = 1$；
对于另外 $10%$ 的评测用例，$K = 2$；
对于另外 $10%$ 的评测用例，$N = 1$；
对于另外 $20%$ 的评测用例，$N, M ≤ 6，K ≤ 5$；
对于另外 $25%$ 的评测用例，$N ≤ 3，M ≤ 20，K ≤ 12$；
对于所有评测用例，$1 ≤ N ≤ 6，1 ≤ M ≤ 100，1 ≤ K ≤ 20$。
输入样例1：
1 2 1输出样例1：
2输入样例2：
4 4 3输出样例2：
276输入样例3：
3 20 12输出样例3：
914051446题解：
这道题正解用状态压缩 $dp$（深搜求方案数的基本上可以用 $dp$ 来更快的解决，毕竟空间换时间嘛），这里使用暴力深搜，虽然只能过一半，但是可以很好的训练深搜回溯算法。
深搜树就是八个分支（对应八个方向）。dfs函数有三个参数，横纵坐标，当前放了多少马。
对于递归出口有两个，一个是我走到最后一行了，不能往下走路，但还没有放到 $k$ 个马的数量；第二个就是我放到了 $k$ 个马的数量。当然还要回溯将放马的地方还原出来（用个bool数组就可以了）。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 110,mod=1e9+7;
int cnt[N][N];
int res=0;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int n,m,k;
void dfs(int x,int y,int sum) //分别枚举棋盘的每个位置放马或不放马。
{
if(sum==k)
{
res=(res+1)%mod;
return ;
}
if(y>m)
{
y=1,x++;
if(x>n) return ;
}
dfs(x,y+1,sum); //(x,y)不放马
if(!cnt[x][y]) //如果(x,y)可以放马，就放马
{
//更新一下状态(在(x,y)处放马后，哪些位置不能放马了)
cnt[x][y]++;
for(int i=0;i<8;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<1||a>n||b<1||b>m) continue;
cnt[a][b]++;
}
dfs(x,y+1,sum+1); //放马后，马的数量sum要 +1
//恢复现场
cnt[x][y]--;
for(int i=0;i<8;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<1||a>n||b<1||b>m) continue;
cnt[a][b]--;
}
}
}
int main()
{
cin>>n>>m>>k;
dfs(1,1,0); //从（1，1）这个位置开始放马，最开始总共放了0个马
printf("%d",res);
return 0;
}
地宫取宝
X 国王有一个地宫宝库，是 $n \times m$ 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 $k$ 件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 $k$ 件宝贝。
输入格式
第一行 $3$ 个整数，$n,m,k$，含义见题目描述。
接下来 $n$ 行，每行有 $m$ 个整数 $C_i$ 用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数，表示正好取 $k$ 个宝贝的行动方案数。
该数字可能很大，输出它对 $1000000007$ 取模的结果。
数据范围
$1 \le n,m \le 50$,
$1 \le k \le 12$,
$0 \le C_i \le 12$
输入样例1：
2 2 2
1 2
2 1输出样例1：
2输入样例2：
2 3 2
1 2 3
2 1 5输出样例2：
14题解：
还是一样，递归求方案数，还是可以用dp解决。但是这里数据小，dfs也可以AC。
每步的数据是坐标位置、手中物品数量、当前物品价值的最大值，因此dfs函数有四个参数
#include<iostream>
using namespace std;
const int N = 55;
int g[N][N];
int n,m,k;
int res;
int MOD = 1000000007;
int dfs(int x,int y,int cnt,int value) //x,y坐标，手里物品数，手里最大价值
{
if(x>n||y>m||cnt>k) return 0; //越界
if(x==n&&y==m) //到达终点
{
if(cnt==k||(cnt==k-1&&g[x][y]>value)) //若在最后手中数量等于k，
return 1; //或者最后手中数量等于k-1且最后的物品价值大于前面所有的物品价值的最大值
else //（意思可以拿最后一件，拿了正好手中物品数量等于k）
return 0;
}
if(g[x][y] > value)
{
return dfs(x+1,y,cnt+1,g[x][y]) + dfs(x,y+1,cnt+1,g[x][y]) + dfs(x,y+1,cnt,value) + dfs(x+1,y,cnt,value);
//取，去下一步，取，去右一步，不取，去右一步，取，去下一步
}
else return dfs(x,y+1,cnt,value) + dfs(x+1,y,cnt,value);
}
int main()
{
cin>>n>>m>>k;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++) cin>>g[i][j];
}
dfs(1,1,0,-1); //表示从(1,1)开始，手中没有物品且价值为-1。
res = dfs(1,1,0,-1)%MOD;
cout<<res;
}
