动态规划
在不碰壁的情况下,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;
}