深度优先搜索和广度优先搜索算法，广度优先搜索(BFS)——马的遍历(洛谷 P1443)

来看一道经典的搜索问题——马的遍历

大致题目，给定棋盘规模，以及马的初始位置，输出马到棋盘的最短距离，若不能到达则输出-1

很简单的一个搜索问题，用经典算法BFS就可以了，唯一需要注意判断的就是马有8种走法，

用一个Next二维数组存放就好。

题目描述

有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入输出格式

输入格式：

深度优先搜索和广度优先搜索算法，一行四个数据，棋盘的大小和马的坐标

输出格式：

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

输入输出样例

输入样例#1： 

3 3 1 1

输出样例#1： 

0    3    2    
3    -1   1    
2    1    4    

解题代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
struct qipan{int xx,yy,steps;
};
int ans[401][401],book[401][401];
int n,m,x,y;
int Next[8][2] = {{-2,1},{-2,-1},{-1,2},{-1,-2},{2,1},{2,-1},{1,2},{1,-2}};
queue<qipan> q;
void print(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(ans[i][j] == 0 && (i!=x || j!=y)){printf("%-5d",-1);}else{printf("%-5d",ans[i][j]);}}printf("\n");}
}
void bfs(){qipan s; s.xx=x; s.yy=y; s.steps=0;int nx,ny,step;q.push(s);book[x][y] = 1;  //初始化状态while(!q.empty()){qipan f = q.front();for(int i = 0;i<8;i++){nx=f.xx+Next[i][0]; ny=f.yy+Next[i][1]; step=f.steps+1;if(book[nx][ny]==0 && nx>=1 && nx<=n && ny>=1 && ny<=m){qipan New;New.xx=nx; New.yy=ny; New.steps=step;q.push(New);  book[nx][ny]=1; ans[nx][ny] = step;}}q.pop();}
}
int main(){cin>>n>>m>>x>>y;bfs();print();return 0;
}

深度优先遍历算法、