@[1906xuzhe](/user/760568) dfs 时间复杂度不对呀，还会爆栈
by OldDriverTree @ 2023-04-28 22:28:35
@[1906xuzhe](/user/760568) 我好像是用的 dfs
然后加一个强行剪枝
by QAQ__ @ 2023-04-28 22:41:06
@[guoxiangyu66](/user/681036) 为啥会爆栈啊
by QAQ__ @ 2023-04-28 22:41:42
@[QAQ__](/user/627636) 奥，我人傻了
by OldDriverTree @ 2023-04-28 23:01:21
```cpp
#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
int n,m,x,y;
int a[405][405];
void dfs(int x,int y,int step)
{
if(step>=201)
{
return;
}
a[x][y]=step;
if(y+1<=m&&x+2<=n&&(a[x+2][y+1]==-1||a[x+2][y+1]>step+1)) dfs(x+2,y+1,step+1);
if(y-1>0&&x+2<=n&&(a[x+2][y-1]==-1||a[x+2][y-1]>step+1)) dfs(x+2,y-1,step+1);
if(y+2<=m&&x+1<=n&&(a[x+1][y+2]==-1||a[x+1][y+2]>step+1)) dfs(x+1,y+2,step+1);
if(y+2<=m&&x-1>0&&(a[x-1][y+2]==-1||a[x-1][y+2]>step+1)) dfs(x-1,y+2,step+1);
if(y-1>0&&x-2>0&&(a[x-2][y-1]==-1||a[x-2][y-1]>step+1)) dfs(x-2,y-1,step+1);
if(y+1<=m&&x-2>0&&(a[x-2][y+1]==-1||a[x-2][y+1]>step+1)) dfs(x-2,y+1,step+1);
if(y-2>0&&x+1<=n&&(a[x+1][y-2]==-1||a[x+1][y-2]>step+1)) dfs(x+1,y-2,step+1);
if(y-2>0&&x-1>0&&(a[x-1][y-2]==-1||a[x-1][y-2]>step+1)) dfs(x-1,y-2,step+1);
}
int main(){
cin>>n>>m>>x>>y;
memset(a,-1,sizeof(a));
dfs(x,y,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<left<<setw(5)<<a[i][j];
}
cout<<endl;
}
}
```
by __phiu @ 2023-04-28 23:46:39
可以尝试迭代加深配合剪枝
by Dog_E @ 2023-04-28 23:56:35
@[Go_Xor](/user/450705) 神犇膜拜。
by 1906xuzhe @ 2023-04-29 22:41:33
@[QAQ__](/user/627636) 又一个神犇
by 1906xuzhe @ 2023-04-29 22:42:21
我是DFS+强行剪枝，
见下表（可以自己画图试试）
| 平移格数 | 1 | 2 | 3 | 4 |
| -----------: | -----------: | -----------: | -----------: | -----------: |
| 所需步数 | 3 | 2 | 3 | 2 |
所以一般情况下每格的答案不会同时大于 m+1 和n+1（理论上这个上限还能更小，但是我懒得算了）
所以在（step > m+1 && step > n+1）时强行停止当前查找
------------
（当然还是建议用BFS，毕竟快是真的快）
------------
贴下蒟蒻代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int ans[405][405];
int n,m;
int xmove[8]={-1,-2,-2,-1,1,2,2,1};
int ymove[8]={2,1,-1,-2,2,1,-1,-2};
//----------------------------------
void dfs(int step,int x,int y)
{
if(step > m+1 && step > n+1) return;
for(int i=0;i<8;i++)
{
if(ans [x+xmove[i]] [y+ymove[i]] <= step && ans [x+xmove[i]] [y+ymove[i]] != -1) continue;
if( x+xmove[i] < 1 || x+xmove[i] > m ) continue;
if( y+ymove[i] < 1 || y+ymove[i] > n) continue;
ans[x+xmove[i]][y+ymove[i]] = step;
dfs( step+1 , x+xmove[i] , y+ymove[i] );
}
}
int main()
{
int x,y;
// cin>>n>>m>>y>>x;
scanf("%d%d%d%d",&n,&m,&y,&x);
memset(ans,-1,sizeof(ans));
dfs(1,x,y);
ans[x][y]=0;
for(int j=1;j<=n;j++)
{
for(int i=1;i<=m;i++)
{printf("%d ",ans[i][j]);}
printf("\n");
}
}
```
by Leo_Anderson @ 2023-05-13 16:06:08