```cpp
#include<bits/stdc++.h>
using namespace std;
bool vis[25][25];
long long step[25][25];//就是 dp 数组
int main()
{
step[1][1]=1;
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;//标记一下马的控制点
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if((i!=1||j!=1)&&!vis[i][j]) step[i][j]=step[i-1][j]+step[i][j-1];//不能走进马的控制点
cout<<step[n][m];
return 0;
}
```
试一下
by him_dream @ 2023-07-03 17:14:22
这道题用dfs的话是O(2^nm)的时间复杂度,y当n=20,m=20时会TLE,建议用递推。
还有代码中
```cpp
if(==1&&v[x+1][y]==1&&x+1<=n)
```
建议改成
```cpp
if(x+1<=n&&a[x+1][y]==1&&v[x+1][y]==1)
```
因为c++中“A&&B”会先判断“A”是否为假
如果x+1>n,a[x+1][y],就会被忽略掉.
还有RE应该是你“马”没有判断是否越界。
可能x0-2会小于0造成RE
by zhuyihao20100712 @ 2023-07-03 17:26:04
@[zhuyihao20100712](/user/957618) 谢谢讲解
by Jiushao @ 2023-07-04 12:46:48
@[frx110925](/user/926841) 好的,感谢
by Jiushao @ 2023-07-04 12:59:54