@[Fang_Juancanyun_A](/user/885060)
可以试着用递推做一下,`dfs`会超时,先把马的位置和马的控制点标为 $-1$,然后遇到控制点直接 `continue`,我是这么写的,您可以参考一下:
```cpp
#include<iostream>
using namespace std;
long long a[1000][1000];
// int dp[21][21];
int nex[8][2] = {
{-2,-1},
{-2, 1},
{-1, 2},
{1, 2} ,
{2, 1} ,
{2, -1},
{1, -2},
{-1,-2}
};
bool vis[1000][1000];
int main()
{
int n, m, x, y;
cin >> n >> m >> x >> y;
vis[x][y] = 1;
for (int i=0; i<8; i++)
{
vis[x+nex[i][0]][y+nex[i][1]] = true;
}
int li = 0, lj = 0;
while (li <= m && !vis[0][li])
{
a[0][li++] = 1;
}
while (lj <= n && !vis[lj][0])
{
a[lj++][0] = 1;
}
for (int i=1; i<=n; i++)
{
for (int j=1;j <= m;j++)
{
if (vis[i][j])
a[i][j] = 0;
else
a[i][j] = a[i][j-1]+a[i-1][j];
// a[i][j] = a[i][j-1] + a[i-1][j];
}
}
cout << a[n][m];
return false;
}
```
by 2058_lunar_fall @ 2023-04-02 19:01:23
好,谢谢
by Feng_Juancanyun_A @ 2023-04-03 21:49:50