这一题dfs本来就是错解，写dp去吧
by EDqwq @ 2020-09-15 18:25:20
@[幽灵特工](/user/332549) 路径的条数最多可以达到 $\dbinom{40}{20}$ 级别，DFS肯定过不了。
by Smile_Cindy @ 2020-09-15 18:26:48
@[幽灵特工](/user/332549) 好像是DFS函数里那个双重循环的逻辑错了（蜜汁自信
by Enterpr1se @ 2020-09-15 18:27:13
DFS+剪枝 也只能得80分，然后TLE，只能写DP或者splay.
by chenqianchun @ 2020-09-15 19:25:06
@[幽灵特工](/user/332549)
如果您一定要用DFS，那么应该逆着推，即采用“自顶向下”的递推方法，同时使用“记忆化”技巧，这实际上是DP的一种形式。常规的是使用“自底向上”式的递推，即两层循环的迭代来控制DP过程。
使用“自顶向下”式递归求解并结合记忆化技巧的参考代码：
```
#include <bits/stdc++.h>
using namespace std;
long long dp[32][32];
long long dfs(int x, int y)
{
if (x < 0 || y < 0) return 0;
if (~dp[x][y]) return dp[x][y];
return dp[x][y] = dfs(x - 1, y) + dfs(x, y - 1);
}
int main(int argc, char *argv[])
{
int tx, ty, kx, ky;
cin >> tx >> ty >> kx >> ky;
memset(dp, -1, sizeof(dp));
dp[0][0] = 1;
for (int i = -2; i <= 2; i++)
for (int j = -2; j <= 2; j++)
if (i * i + j * j == 5 && (kx + i) >= 0 && (ky + j) >= 0)
dp[kx + i][ky + j] = 0;
dp[kx][ky] = 0;
cout << dfs(tx, ty) << '\n';
return 0;
}
```
by metaphysis @ 2020-09-15 19:26:30
@[metaphysis](/user/333388) 您能详细解释一下两层for循环为什么赋此初值，和循环内的if的判断条件吗？
by 幽灵特工 @ 2020-09-16 12:21:35
我的代码在本地能编译，但洛谷不能编译通过。这是为什么？
by 幽灵特工 @ 2020-09-16 12:22:16
@[幽灵特工](/user/332549) 我自己看懂了。相对于我对八个点的八行代码，您的写法真妙！
by 幽灵特工 @ 2020-09-16 12:29:53
@[metaphysis](/user/333388)
我这样写有什么问题吗？
```cpp
#include <bits/stdc++.h>
using namespace std;
long long dp[21][21]={0};
long long visit[21][21]={0};
int a,b,c,d;
long long sol(int dx,int dy){
if(dx<0||dy<0)return 0;
if(visit[dx][dy])return dp[dx][dy];
dp[dx][dy]=sol(dx-1,dy)+sol(dx,dy-1);
visit[dx][dy]=1;
return dp[dx][dy];
}
int main(){
dp[0][0]=1;
cin>>a>>b>>c>>d;
for(int i=-2;i<=2;i++){
for(int j=-2;j<=2;j++){
if(i*i+j*j==5){
dp[c+i][d+j]=0;
}
}
}
dp[c][d]=0;
cout<<sol(a,b);
}
```
by 幽灵特工 @ 2020-09-16 12:47:46
@[幽灵特工](/user/332549)
```
#include <bits/stdc++.h>
using namespace std;
// 数组范围要大一些，要不然会导致越界。
long long dp[32][32]={0};
long long visit[32][32]={0};
int a,b,c,d;
long long sol(int dx,int dy){
if(dx<0||dy<0)return 0;
if(visit[dx][dy]) return dp[dx][dy];
dp[dx][dy]=sol(dx-1,dy)+sol(dx,dy-1);
visit[dx][dy]=1;
return dp[dx][dy];
}
int main(){
// 标记起点已经计算。
visit[0][0] = 1;
dp[0][0]=1;
cin>>a>>b>>c>>d;
for(int i=-2;i<=2;i++){
for(int j=-2;j<=2;j++){
// 注意不要忘了范围检查，网格类的题目，这是常规操作。
if(i*i+j*j==5 && c + i >= 0 && d + j >= 0){
dp[c+i][d+j]=0;
// 标记马能控制的点为已经访问，表示一遇到此点即可返回。
visit[c + i][d + j] = 1;
}
}
}
dp[c][d]=0;
// 标记马本身的位置为已经访问。
visit[c][d] = 1;
cout<<sol(a,b);
}
```
有空请您访问我的 [CSDN博客](https://blog.csdn.net/metaphysis)，里面有我写的一本书，内有编程竞赛相关内容的介绍，并附有对应的练习题目（题目源自UVa OJ），可免费下载此书的PDF版本：[《C++，挑战编程——程序设计竞赛进阶训练指南》](https://blog.csdn.net/metaphysis/article/details/90288252)。
by metaphysis @ 2020-09-16 14:23:01