2.过河卒

题目：
棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A 点 (0,0),B 点 (n,m)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式
一行四个正整数，分别表示 B 点坐标和马的坐标。
输出格式
一个整数，表示所有的路径条数。

dp思路
设当前点为（i，j）
最优子结构：(i-1,j) (i,j-1)两种路径可以到达
状态转移方程：（i，j） = (i-1,j)或(i,j-1)
边界 ：B 点 (n,m)，以及特殊情况马的范围

//01

include

using namespace std;
/
1.标记马的范围
2.遍历点 /
bool vis[25][25];
long long dp[25][25];
int main(){
int n,m,x,y;
cin>>n>>m>>x>>y;
n++;
m++;
x++;
y++;
vis[x][y] = 1;
vis[x-2][y-1]=1;
vis[x-2][y+1]=1;
vis[x+2][y-1]=1;
vis[x+2][y+1]=1;
vis[x-1][y+2]=1;
vis[x-1][y-2]=1;
vis[x+1][y+2]=1;
vis[x+1][y-2]=1;

dp[0][1] = 1;
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        if(!vis[i][j]){
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
}
cout<<dp[n][m];

}

题目本质：
求一点到另一条点在一些限制下总共有多少条路径
数学方法：标数法
相当于 走到该点的路径数量等于该点的上边点和右边点的标数和，和即为该点的标数
具体详见
https://zhuanlan.zhihu.com/p/110868668

dp思想：
用vis[][]来当作遍历时的限制
dp[][]作为中间结果，直至到遍历到目标