洛谷 P1443 马的遍历
嗯....
这道题是一个标准的bfs，只要背过了bfs 的模板，这道题小菜一碟...
首先先看题目：
题目描述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入输出格式
输入格式：
一行四个数据，棋盘的大小和马的坐标
输出格式：
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
输入输出样例
输出样例#1：
0 3 2 3 -1 1 2 1 4
首先先讲一下思路：
首先 bfs 肯定要用队列，两个队列分别存点的横、纵坐标，然后用nx和my两个数组分别存储马下一步能到达的方向，vis数组判断是否访问，
ｇ数组存棋盘，马每到一个点，首先将vis变为１,并且将横、纵坐标入队，然后进行bfs，将能一步到达的点储存，并且判断它是否越界，
然后是否将其入队，最后输出结果即可...
能想到用nx和ny两个数组来存储马前进的方向是此题的重点，能背过 bfs 的模板是此题前提与关键
下面是AC代码，外加解析：
1 #include<cstdio>
2 //#include<iomanip>
3 #include<iostream>
4 #include<queue>
5 #include<cstring>
6
7 using namespace std;
8
9 int g[401][401];//存棋盘
10
11 queue <int> q, q1;//q队列存横坐标,q1队列存纵坐标
12
13 int nx[8] = {1,2,2,1,-1,-2,-2,-1};//表示马横坐标的八种变化
14 int my[8] = {2,1,-1,-2,-2,-1,1,2};//表示马纵坐标的八种变化，为此题的重点
15 bool vis[401][401]; //是否访问
16
17 int main(){
18 int n, m;
19 int x, y;
20 memset(g,-1,sizeof(g));//初始化棋盘
21 scanf("%d%d",&n,&m);
22 scanf("%d%d",&x,&y);
23 g[x][y] = 0;
24 vis[x][y] = 1;
25 q.push(x);
26 q1.push(y);
27 // 开始进行 bfs，此题的框架
28 while (!q.empty() ){
29 int u = q.front();//将先前一个马的位置存储下来
30 int v = q1.front();
31 q.pop();
32 q1.pop();
33 for(int i = 0; i <= 7; i++){
34 int x1 = u + nx[i];//更新马的位置
35 int y1 = v + my[i];
36 if (x1 > 0 && x1 <= n && y1 > 0 && y1 <= m && vis[x1][y1] == 0)//判断是否越界和是否被访问过
37 {
38 vis[x1][y1] = 1;
39 g[x1][y1] = g[u][v] + 1;// 到达此点的步数等于到达上一个点的步数加一
40 q.push(x1); //将新的位置入队
41 q1.push(y1);
42 }
43 }
44 }
45 for(int i = 1; i <= n; i++){
46 for(int j = 1; j <= m; j++){
47 printf("%-5d",g[i][j]);
48 //cout<<left<<setw(5)<<g[i][j];
49 }
50 printf("
");
51 }
52 return 0;
53 }
在这道题中，最终的输出方式与往常不同，请见下：
左对齐宽5格可以有两种输出方法：
1.使用printf:
(1)对齐：
printf中的左对齐表示为在%后加-
printf中的右对齐表示为在%后加+
(2)宽ｘ格：(x为数)
printf中的宽x格表示为在对齐符号后加x
2.使用cout:
注意：
cout中的操作简单，但比较慢，并且在使用cout做上述操作时，需要加头文件 <iomanip>