洛谷 P1443 马的遍历 刷题笔记 BFS
一道搜索题 从第一个点一层一层往外搜索 即最少步数
分析题目我们都知道马走日
画图定义出搜索的八个方向
所以
int dir[8][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},
{1,-2},{1,2},{2,-1},{2,1}}
开搜
BFs模板分析
BFS
#include<bits/stdc++.h>
#include<queue>
Using namespace std;
#define check(x,y) (x > 0 && x <= n && y >0 && y <= m && b[x][y] == false) //越界判断 1
Queue<int> qx,qy;//不能用带两个int 的node结构体队列 否则内存会爆掉 2
Void bfs(int dx,int dy){
Bool[dx][dy]=true;//标记为已经访问 3
Qx.push(dx);//第一个点入队完成初始化 4
Qy.push(dy);
While(!qx.empty()){
Int tx = qx.front();//取出队头 5
Int ty = qy.front();
Qx.pop();//拿出来 进行处理之后 将队头删掉 6
Qy.pop();
For(int i=0;i<8;i++){
int nextx = tx =dir[i][0];
int nexty = ty =dir[i][0];
If(check(nextx,nexty)){
Qx.push(nextx);//加入队尾 7
Qy.push(nexty);
Bool[nextx][nexty]=true;//标记为已经访问 8
}
}
}
完整代码
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int dir[8][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},
{1,-2},{1,2},{2,-1},{2,1}};
const int N = 410 ;
int a[410][410] = {0};
bool b[410][410];
#define check(x,y) (x > 0 && x <= n && y >0 && y <= m && b[x][y] == false)
queue<int> q,q1;
int n,m,x,y,step;
void bfs(int dx,int dy){
int step = 0;
q.push(dx);
q1.push(dy);
b[dx][dy] = true ;
while(!q.empty()){
int tx = q.front() ;
int ty = q1.front() ;
q.pop();
q1.pop();
for(int i = 0 ;i < 8;i++){
int nx = tx + dir[i][0];
int ny = ty + dir[i][1];
if(check(nx,ny)){
b[nx ][ny ] = true ;
a[nx][ny ] = a[tx][ty]+1 ;
q.push(nx);
q1.push(ny);
}
}
}
}
int main(){
cin>>n>>m>>x>>y;
bfs(x,y);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(i == x && j == y){
cout<<0<<' ';
}else if(a[i][j] != 0){
cout<<a[i][j]<<' ';
}else{
cout<<-1<<' ';
}
}cout<<endl;
}
return 0;
}
}
原文地址：https://blog.csdn.net/2301_78763076/article/details/145203439
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！