一遍bfs就行了
by zyh0516_lucky @ 2023-10-11 18:04:33
大佬太强了%%%。
本蒟蒻才0分。
@[def_int_long_long](/user/657210)
by This_is_End @ 2023-10-11 18:05:39
就是这么简单
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
ll x,y;
};
ll n,m,x,y;
ll dxy[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};
ll ans[405][405];
queue<node> q;
int main() {
cin>>n>>m>>x>>y;
memset(ans,-1,sizeof ans);
ans[x][y]=0;
q.push({x,y});
while(!q.empty()){
node t=q.front();
for(int i=0;i<8;i++){
ll nwx=t.x+dxy[i][0],nwy=t.y+dxy[i][1];
if(ans[nwx][nwy]!=-1||nwx<1||nwx>n||nwy<1||nwy>m) continue;
q.push({nwx,nwy});
ans[nwx][nwy]=ans[t.x][t.y]+1;
}
q.pop();
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cout<<ans[i][j]<<" ";
cout<<endl;
}
return 0;
}
```
by zyh0516_lucky @ 2023-10-11 18:08:03
大概是这样的:你的 bfs 在计算的时候实际上会重复计算,造成不必要的运算,所以可以看楼上的代码直接 bfs 1 次,遍历到所有点,直接更新 ans 数组。
by _tan_ @ 2023-10-12 07:21:12
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
ll x,y;
};
ll n,m,x,y;
ll dxy[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};
ll ans[405][405];
queue<node> q;
int main()
{
cin>>n>>m>>x>>y;
memset(ans,-1,sizeof ans);
ans[x][y]=0;
q.push({x,y});
while(!q.empty())
{
node t=q.front();
for(int i=0;i<8;i++)//枚举当前点所能跳到的点
{
ll nwx=t.x+dxy[i][0],nwy=t.y+dxy[i][1];
if(ans[nwx][nwy]!=-1||nwx<1||nwx>n||nwy<1||nwy>m)continue;
//判断点的合法性以及没有被遍历过
q.push({nwx,nwy});
ans[nwx][nwy]=ans[t.x][t.y]+1;
//更新ans数组中的最终解
}
q.pop();
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<ans[i][j]<<" ";
cout<<endl;
}
return 0;
}
//思想:根据当前点所能影响到的所有点,更新那些点的答案
```
解释的是楼上的
by _tan_ @ 2023-10-12 07:24:11