过河卒——（披着搜索皮的动态规划）

题目传送门

废话：

开始以为是一道dfs，写了结果超时，只过了两个样例，这道题牛客寒假训练营的时候做过，当时没做出来，后来补上了。过了这么久又把他当成dfs了，思路参考某大佬
大佬博客

思路：

1小兵只能往下或者右边走，用二维数组a来表示到达这个点的路径条数
2由小兵的行走方式，可以推出状态转移方程
a[i][j] = a[i-1][j] + a[i][j-1] (到达这个点的路径条数等于到达它上一个点和左边的点的路径条数之和）
3有些细节处理注意代码注释

代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 30;
int b[maxn][maxn]={0};
long long a[maxn][maxn]={0};
int dx[10]={2,1,-1,-2,-2,-1,1,2};
int dy[10] = {1,2,2,1,-1,-2,-2,-1};
int n,m,Bx,By;
int  check(int x,int y)
{
    return (x>=0&&x<=Bx&&y>=0&&y<=By)?1:0;
}
int main()
{
    cin>>Bx>>By>>n>>m;
    //设置障碍
    b[n][m] = 1;
    for(int i=0;i<8;i++)
    {
        int x2 = n + dx[i];
        int y2 = m + dy[i];
        if(check(x2,y2)) b[x2][y2] = 1;
    }
    //预处理第0列,第0行
    //这里一定要注意，如果遇到了马能到达的点，就直接break
    //因为小兵只能往右或者往下，例如往右，遇到了马能到达的点（0，j)
    //这个点及其右边的点，小兵都不能到达了，因为它不能后退或者往左走
   for(int i=0;i<=Bx;i++)
    {
        if(b[i][0]) break;
           a[i][0] = 1;
    }

   for(int i=0;i<=By;i++)
    {
        if(b[0][i]) break;
         a[0][i] = 1;
   }

   for(int i=1;i<=Bx;i++)
   {
       for(int j=1;j<=By;j++)
       {
           if(b[i][j]) a[i][j] = 0;//遇到了马能到达的点，那么小兵不能经过这里，所以置为0
           else a[i][j] = a[i-1][j] + a[i][j-1];
       }
   }
   cout<<a[Bx][By];
    return 0;
}