这题我用dp做的,dp方程为dp[i][j]=dp[i-1][j]+dp[i][j-1]
by chensiru @ 2023-05-28 14:15:55
```cpp
#include <bits/stdc++.h>
using namespace std;
int i,j;
const int maxn=20+5;
int judge[maxn][maxn];
long long go[maxn][maxn]= {1};
int main()
{
memset(go,0,sizeof(go));
memset(judge,0,sizeof(judge));
int n,m,a,b;
cin>>n>>m>>a>>b;
judge[a][b]=1;
judge[a+2][b+1]=1;
judge[a+2][b-1]=1;
judge[a+1][b+2]=1;
judge[a+1][b-2]=1;
judge[a-2][b+1]=1;
judge[a-2][b-1]=1;
judge[a-1][b+2]=1;
judge[a-1][b-2]=1;
for(i=1; i<=n; i++)
if(judge[i][0]==0)
go[i][0]=1;
else
break;
for(i=1; i<=m; i++)
if(judge[0][i]==0)
go[0][i]=1;
else
break;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
if(judge[i][j]==0)
go[i][j]=go[i-1][j]+go[i][j-1];
cout<<go[n][m]<<endl;
return 0;
}
```
这道题用DFS不太现实,毕竟也是类似于递归的方法。我的解法和楼上有些相似,毕竟状态转移方程都是:
```cpp
f[i][j]=f[i-1][j]+f[i][j-1]
```
这个方程算是非常好写的了,只要你上过小学都知道,我就不一一说明了
总之,希望我的答案会对你有帮助
by _Adolf_Hitler_ @ 2023-05-28 14:48:37
@[chensiru](/user/817525) +1
by __ii__ @ 2023-05-28 15:07:06
@[JODAN_POOLE](/user/931106)
思路可以get到,可以说一下前两个for里面的“else break;”的作用吗?
by luoyuwei @ 2023-05-28 15:24:12
@[JODAN_POOLE](/user/931106)
照着写的时候出了2个RE,后来在标记马每个到达位置的时候加入了防溢出if语句,就过了!‘
谢谢^_^
by luoyuwei @ 2023-05-28 15:38:12
@[luoyuwei](/user/678057)
不是溢出,是越界
by luoyuwei @ 2023-05-28 15:39:14
bfs
by Tx1234567 @ 2023-06-01 19:44:20