马的遍历
思路:首先要知道马走日字,可以走8个方向.
建立数组a和数组b,分别表示马一步可以走的横纵坐标的对应长度。
然后从马的起始位置(队首)开始向周围扩展,并依次记录步数。若扩展到的点在棋盘里且没有被搜到过,就入列。
当队首向外扩展完了,让当前队首出队,再由下一个队首继续向外扩展寻找.最后如果没被搜到的点输出-1。
代码如下:
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
const int N=410;
int n,m,sx,sy;
int map[N][N];//存放棋盘中每点到达步数，还有判重功能
int dx[8]={1,1,-1,-1,2,2,-2,-2};
int dy[8]={2,-2,2,-2,1,-1,1,-1};//围棋马能走的八个方向
/*或者开一个二维数组int dd[8][2]={{1,2}，{1，-2}，{-1,2}....}
dd[][0]就等于dx[]；dd[][1]就等于dy[] */
struct Node{
int x;
int y;
int step;
};//将每个点的位置和达到所用步数打包成Node类型（结构体）
int main(){
cin>>n>>m>>sx>>sy;
queue<Node>Q;//定义一个Node类型的队列 ,放点
Q.push((Node){sx,sy,0});//将初始点信息压进队首
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
map[i][j]=-1;
}//将棋盘步数都变成-1，走不到的点就会一直是-1
map[sx][sy]=0;//从初始点出发广搜，将初始点步数变成0
while(!Q.empty()){//当队列不为空时,开始bfs
for(int i=0;i<8;i++){//八个方向广搜
int xx=Q.front().x+dx[i];//Q.front()返回第一个元素
int yy=Q.front().y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&map[xx][yy]==-1)//如果搜到的点在棋盘里且没有被搜到过 在边界内
{ Q.push((Node){xx,yy,Q.front().step+1});//将能走到的点压入队列
map[xx][yy]=Q.front().step+1;//步数更新
}
}
Q.pop();//当队首的下一层可以走到的点全部放入队列后，队首(起始点)踢出
}
for(int i=1;i<=n;i++){//按格式输出
for(int j=1;j<=m;j++)
printf("%5d",map[i][j]);
printf("\n");
}
return 0;
}
标签：Node,map,遍历,int,xx,front,步数 From： https://www.cnblogs.com/xdzxyingrui/p/16619751.html