动态规划

在不碰壁的情况下,f[ i, j ] 可以由
①f[ i-2, j-1 ] 向上2步，向右1步
②f[ i+2, j-1 ] 向下2步，向右1步
③f[ i-1, j-2 ] 向上1步，向右2步
④f[ i+1, j-2 ] 向下1步，向右2步
这四种情况走过来
于是我们把这四种情况加起来，就能得到所有种不同的路径
我们从(1,1)这个点出发，所以让f[1,1]=1
再通过循环不断更新从起点到每一个点的总不同路径数
最后输出 f [n, m] 即可

需要注意的是，由于它水平方向上只能从左往右走，而竖直方向任意，所以对列的遍历放在外循环，对行的遍历放在内循环
举个栗子，从(1,1)走到(4,5)只有一条路：f[1,1]->f[3,2]->f[2,4]->f[4,5]
如果我们把对行的遍历放在外循环，对列的遍历放在内循环的话，
i=2时, f[2,4] 由 f[3,2] 走来，但此时第3行还未更新到，但它其实会在i=3时由f[1,1]走来

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int N = 20;
int f[N][N];


int main()
{
    cin>>n>>m;
    
    f[1][1]=1;

    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
        {
            if(j-1>=1)
            {
                if(i-2>=1) f[i][j] += f[i-2][j-1];
                if(i+2<=n) f[i][j] += f[i+2][j-1];
            }
            if(j-2>=1)
            {
                if(i-1>=1) f[i][j] += f[i-1][j-2];
                if(i+1<=n) f[i][j] += f[i+1][j-2];
            }
        }
    
    cout<<f[n][m];
    
    
    return 0;
}