bfs用队列的吗?
by luochengyi @ 2024-01-24 14:15:00
@[luochengyi](/user/730900) 不是要用队列吗?
by luochengyi @ 2024-01-24 14:15:44
@[luochengyi](/user/730900) 对的啊,我用的队列
by dongran @ 2024-01-24 14:17:54
@[dongran](/user/933946) 你的`q`数组好像是`pair`类型的,存值时要用`make_pair`
by danlao @ 2024-01-24 14:18:28
@[dongran](/user/933946) 我写的是正宗`BFS`,你可以对照一下
```cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define FOR(i,j,n,k) for(int i=(j);i<=(n);i+=k)
#define ROR(i,j,n,k) for(int i=(j);i>=(n);i-=k)
const int dx[8]={-1,-2,-2,-1,1,2,2,1};
const int dy[8]={2,1,-1,-2,2,1,-1,-2};
int n,m;
int map[410][410];
struct csp{
int x,y,a;
};
bool vis[410][410];
bool check(int x,int y){
return (x>=1&&x<=n&&y>=1&&y<=m);
}
int bfs(int x,int y,int a){
queue<csp> q;
q.push((csp){x,y,a});
while(!q.empty()){
x=q.front().x;
y=q.front().y;
a=q.front().a;
q.pop();
if(vis[x][y]) continue;
vis[x][y]=1;
map[x][y]=a;
FOR(i,0,7,1){
int tx=x+dx[i];
int ty=y+dy[i];
if(check(tx,ty)) q.push((csp){tx,ty,a+1});
}
}
return -1;
}
int main(){
int x,y;
scanf("%d%d%d%d",&n,&m,&x,&y);
memset(map,-1,sizeof(map));
int d=bfs(x,y,0);
FOR(i,1,n,1){
FOR(j,1,m,1){
if(i==x&&j==y){
printf("%-5d",0);
continue;
}
printf("%-5d",map[i][j]);
}
printf("\n");
}
return 0;
}
```
by danlao @ 2024-01-24 14:21:37
`d`变量没用,不用管
by danlao @ 2024-01-24 14:22:31
@[yaodiguoan](/user/1023793) ok,谢谢啦
by dongran @ 2024-01-24 14:25:21
~~这道题什么时候升黄的我都不知道~~
by danlao @ 2024-01-24 14:25:24
调了一会,发现下标出现问题了。(?当作0开始的!!)
------------
这是正确版本:
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=410;
int g[N][N];
PII q[N*N];
int n,m,x,y;
void bfs(int x,int y){
int hh=0,tt=0;
q[0]={x,y};
g[x][y]=0;
int dx[8]={1,2,2,1,-1,-2,-2,-1};
int dy[8]={2,1,-1,-2,-2,-1,1,2};
while(hh<=tt){
auto t=q[hh++];
for(int i=0;i<8;i++){
int sx=t.x+dx[i];
int sy=t.y+dy[i];
if(sx<=0||sx>n||sy<=0||sy>m) continue;
if(g[sx][sy]!=-1) continue;
g[sx][sy]=g[t.x][t.y]+1;
q[++tt]={sx,sy};
}
}
}
int main(){
cin>>n>>m>>x>>y;
memset(g,-1,sizeof(g));
bfs(x,y);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<g[i][j]<<" ";
}
puts("");
}
return 0;
}
```
by dongran @ 2024-01-24 15:15:34