1.题目解析

题目来源：过河卒——牛客 

测试用例 

2.算法原理

1.状态表示

本题是动态规划中的路径问题，创建dp表并且每个位置的含义是以该位置为终点的最大路径数

2.状态转移方程

每个位置的路径数是由上面位置个左边位置的路径数之和得来的，所以可以得到初步的状态转移方程为：dp[i,j] = dp[i-1][j]+dp[i][j-1]

但是此时需要注意在马的位置以及马一步可以跳到的位置是不能走的，所以需要判断当不会遇到马才可以使用上面的状态转移方程，如果遇到则该位置路径数为0，如下图

3.初始化

这里额外多开辟一行一列虚拟位置可以直接在循环内部初始化dp表，需要注意的是dp表实际数据的第一个位置的上面或者左边的虚拟位置需要置为1，其他位置则置为0即可

4.填表顺序

这里填表顺序是从上至下，每一行从左到右，还要注意细节就是图上的坐标实际上比创建的dp表坐标会多1，这是因为图中是以格子为下标，而dp表是以节点为下标

5.返回值 

返回dp[m+1][n+1]

3.实战代码

#include<iostream>
using namespace std;

int n,m,x,y;
long long dp[25][25];

int main()
{
    cin>>n>>m>>x>>y;
    dp[0][1] = 1;
    x += 1; y += 1;
    for(int i = 1;i <= n+1;i++)
    {
        for(int j = 1;j <= m+1;j++)
        {
            if(i != x && j != y && abs(i - x) + abs(j - y) == 3
              || (i == x && j == y))
            {
                dp[i][j] = 0;
            }
            else
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    cout<<dp[n+1][m+1];
    
    return 0;
}