过河卒

题目

A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。
同时在棋盘上的 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。
卒不能通过对方马的控制点。
棋盘用坐标表示，A 点 (0,0)、B 点 (n,m)（n<21，m<21），C 点 (x,y)。
约定：C 点不与 A 点或 B 点重合。
现在要求计算出卒从 A 点能够到达 B 点的路径的条数。

解题思路

马跳日。计算出对方马的控制点。

运用动态规划思想：
dp[i][j] 表示从点 (0,0) 到达点 (i,j) 时路径的条数。则状态转移方程为：
如果 (i,j) 是对方马的控制点，那么 dp[i][j] = 0；
否则，dp[i][j] = dp[i-1][j] + dp[i][j-1]。

C++代码

#include<iostream>
#include<vector>
#include<set>
using namespace std;

typedef unsigned long long ULL;

int main(){
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    int d[8][2] = {{1,2}, {-1,2}, {1,-2}, {-1,-2}, {2,1}, {2,-1}, {-2,1}, {-2,-1}};
    set<pair<int,int>> st;
    st.insert(make_pair(x,y));
    for(int i=0; i<8; ++i){
        st.insert(make_pair(x+d[i][0], y+d[i][1]));
    }
    vector<vector<ULL>> dp(n+1, vector<ULL>(m+1,0));
    dp[0][0] = 1;
    for(int i=0; i<=n; ++i){
        for(int j=0; j<=m; ++j){
            if(st.find(make_pair(i,j))==st.end()){
                if(i>0)
                    dp[i][j] = dp[i-1][j];
                if(j>0)
                    dp[i][j] += dp[i][j-1];
            }
            else{
                dp[i][j] = 0;
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}