传送门
大致题意 : 在原点处有一点卒A, A要从棋盘中走某路线到达B点, 棋盘中有一马, 卒要避开马的自身位置以及马能走到的位置, 问从A到B有多少路线
分析 : 基础dp, 卒每次能向右走或向下走, 可以推出状态转移f[i][j] 表示从A到(i, j)的方案数, 属性为数量, 状态转移方程, f[i][j] = f[i-1][j] + f[i][j-1](即从上方或左侧转移过来), (所有坐标加1, 方便计算)初始化 f[1][1] = 1, 开一个st数组记录马的控制点, 当遇到马的控制点是跳过即可, 数据较大注意开ll
ac代码如下 :
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <queue>using namespace std;typedef long long ll;
typedef pair<int, int> PII;const int N = 22;int n, m, x, y;
ll f[N][N]; // 状态转移方程 f[i][j] = f[i-1][j] + f[i][j-1]
bool st[N][N];
int dx[8] = {1,2,1,2,-1,-2,-1,-2};
int dy[8] = {2,1,-2,-1,2,1,-2,-1};int main()
{scanf("%d%d%d%d", &n, &m, &x, &y);n++; m++; x++; y++;st[x][y] = 1;for(int i = 0; i<8; i++){int a = x+dx[i], b = y+dy[i];if(a>0 && a<=n && b>0 && b<=m) st[a][b] = 1;}f[1][0] = 1;for(int i = 1; i<=n; i++){for(int j = 1; j<=m; j++){if(st[i][j]) continue;f[i][j] = f[i-1][j] + f[i][j-1];}}cout<<f[n][m]<<endl;
}