你好，我是gwg725。
洛谷账号：
欢迎与我讨论。：）
题目描述：
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的某一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。
输入：
给出n、m和C点的坐标。
输出：
从A点能够到达B点的路径的条数。
序言：
好了，题目读完了。这道题是我入门dp第一道关键，也是我独自一人在看了关于dp相关资料下想了半个小时题目，所以我认为这道题极有意义，就写了文章。刚开始的话，我没看你谷的算法标签，莽着写搜索代码，代码是这样子的：
#include<bits/stdc++.h>
using namespace std;
int fx[9]={0,1,1,2,2,-2,-2,-1,-1};
int fy[9]={0,2,-2,1,-1,1,-1,2,-2};
int dx[3]={0,1,0};
int dy[3]={0,0,1};
int n,m;
int mx,my;
bool b[20][20];
int cnt=0;
void dfs(int step,int x,int y)
{
if(x==n&&y==m)
cnt++;
b[x][y]=1;
for(int i=1;i<=2;i++)
{
int x_x=dx[i]+x;
int x_y=dy[i]+y;
if(x_x>=0&&x_x<=n&&x_y>=0&&x_y<=m&&b[x_x][x_y]==0)
dfs(step+1,x_x,x_y);
}
b[x][y]=0;
}
int main()
{
cin>>n>>m>>mx>>my;
for(int i=0;i<=8;i++)
{
int xm=fx[i]+mx;
int ym=fy[i]+my;
b[xm][ym]=1;
}
dfs(0,0,0);
cout<<cnt;
return 0;
}
不出所料，只得了60分。当时的我也很蒙圈，第一个问题，就是我的数组开小了。由于从1开始，所以二维数组不能是[20][20]，要扩大一点防止数组溢出。
解决完了后，我却还是只有80分，始终改不定，这个时候我才去查看算法标签，这才发现要用坐标dp动态规划。
自那以后，我便开始了dp学习之路。
正文：
我在小学学过一点奥数，知道怎么去算路径条数，所以学坐标dp稍微轻松一点。
没有学过的同学可能很难理解其中的奥妙，所以说我这里做一下解释，请读者朋友耐心看完，这可能对你的学习有很大的作用。
提示：不提倡复制粘贴式题解刷题法，这是自欺欺人的行为，对学习毫无帮助。
我们从最基础的开始解释。
如图，这是一个平面直角坐标系（C++），左上角的坐标为（0，0），右下角的坐标为（2，4）。
上文说道这是一种小奥题目，大体上非常简单。当时的我怎么也不会想到，这东西竟然是一个宏观的坐标型动态规划。（注：这里默认只能走右边或下边）
上图是每一个点从（0，0）可以到达的路径条数，你发现规律了吗？
没错，每一个点从（0，0）可以到达的路径条数为（上面那个点从（0，0）可以到达的路径条数）+（右边那个点从（0，0）可以到达的路径条数）
所以易得动态转移方程式为：
与此同时，可得到代码：
#include<bits/stdc++.h>
using namespace std;
int dp[114][114];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 0;i<=n;i++){
dp[i][0] = 1;
}
for(int i = 0;i<=m;i++){
dp[0][i] = 1;
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
cout << dp[n][m];
return 0;
}好了，这是一个粗略的路径求过程，现在你应该会了吧？
我们再看回题目，马拦住了过河卒，这不就是把马本身以及它可能回跳到的店遍历一下吗？废话不多说，上代码：
注意！！！！别复制粘贴！！！！你会棕掉
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[50][50];
int a[50][50];
int n,m;
int mx,my;
signed main()
{
scanf("%lld%lld%lld%lld",&n,&m,&mx,&my);
n++;
m++;
mx++;
my++;
dp[1][1] = 1;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(i == 1&&j == 1) continue;
if((i == mx&&j == my)||(i == mx+1&&j == my+2)||(i == mx-1&&j == my+2)
||(i == mx+1&&j == my-2)||(i == mx-1&&j == my-2)||(i == mx-2&&j == my+1)||(i == mx+2&&j == my-1)
||(i == mx+2&&j == my+1)||(i == mx-2&&j == my-1)) dp[i][j] = 0;
else dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
cout << dp[n][m];
return 0;
}