分析

题目：如图，小码君站在A点，他想去找小码酱玩，小码酱在B点。小码君的行走是有规则的：可以向下、或者向右。
同时小码酱在棋盘上的任一点放了一个的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为马的控制点。例如上图C点上的马可以控制9个点（图中的P1，P2...P8和C）。小码君不能通过对方的控制点。
棋盘用坐标表示，A点（0，0）、B点（n, m）(n,m为不超过20的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定：C!=A，同时C!=B）。现在要求你计算出小码君从A点能够到达B点的路径的条数。

思路

本题可以使用二维动态规划，先标记出每个控制点，然后再遍历所有点进行累加路径。因为只能往右和下，所以能到一个点的路径就是上面一格路径数量加上左边数量的和，得到状态转移方程：$dp[i][j] = max(dp[i][j],dp[i-1][j] + dp[i][j-1])$。注意，鉴于指数级累加，本题相关数据必须使用 $long$ $long$ 类型。

---

代码

#include <iostream>
using namespace std;

long long n,m,x,y,dp[25][25];
bool mp[25][25];

int main(){
    cin >> n >> m >> x >> y;
    n++; m++; x++; y++;
    mp[x][y] = true;
    mp[x+2][y+1] = true;
    mp[x+1][y+2] = true;
    mp[x-1][y+2] = true;
    mp[x-2][y+1] = true;
    mp[x-2][y-1] = true;
    mp[x-1][y-2] = true;
    mp[x+1][y-2] = true;
    mp[x+2][y-1] = true;
    dp[1][1] = 1;
    for (int i = 1;i <=n;i++){
        for (int j = 1;j <= m;j++){
            if (!mp[i][j]){
                dp[i][j] = max(dp[i][j],dp[i-1][j] + dp[i][j-1]);
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

---

2024年12月08日 版本1