洛谷刷题记——P1443 马的遍历

这是一道非常简单的BFS模板题，搜索入门学员可以用这道题练练手。

题目描述

见“P1443 马的遍历”。

知识链接

广度优先搜索（BFS）

BFS（Breath First Search，广度优先搜索，简称广搜）是一种与DFS相对的搜索方法，可以用以下的例子理解它：一颗石子被投入水面中，激起层层涟漪扩散。广搜，顾名思义，是先搜完当前这一层，再去搜下一层，而不是“一条路走到黑”。BFS有些类似于并行计算，但显然OI并不支持并行计算，所以我们需要用单行计算来模拟并行计算，而要做到这一点，我们需要一个利器——队列（Queue）。是的，由于队列先进先出（First In First Out，FIFO）的特点，简直是BFS的绝配。当然，我也讲不清楚这些，大家可以自行上网Google。

解题思路

刚才说了，这就是一道BFS的裸题。由于BFS的特点，导致第一次搜到某个点就可以确定搜索所用的次数一定就是最短路。

有一些小细节：一个就是马的行走问题。可以一个一个分别走、再用if判断，但一种更简便的方法是将马每次行走的坐标变化存入数组中，然后用一个for循环每次加上坐标变化就行了（具体实现可见代码）。注意：一定要判断坐标是否越界！！！

另一个就是路径要额外存。虽然由于BFS的特性，第几轮迭代就可以确定这个点的最短路径是第几，但是由于BFS的循环次数与第几轮迭代并没有关系，所以我们要将这个点是第几轮搜到的存入结构体（或另开一个数组存），这个数就是这个点的最短路径，然后它的子节点的最短路径就是这个数＋1。

最后一个，本题要求格式化输出，像表格一样。由于本人不会printf的格式化输出（蠢），于是使用了一种取巧（笨）的方式：由推算可知，每格最大长度为5位，于是输出每个数后就输出(5 – 这个数的长度)个空格就行了。至于如何获取这个数的长度，可以专门写一个函数来算，但我们决定使用一种简便（慢死了）的办法：将这个数转为字符串，然后用STL自带的size()方法求出字符串的长度。

// string to_string(int n) 的作用是将n转换为字符串，具体如何使用可以Google一下
// str.size() 的作用是返回一个字符串的长度，str是一个已经定义好的字符串
to_string(num).size(); // 求num的长度

代码展示

拒绝抄袭，共创和谐社会[机智]

#include <cstdio> // std::scanf, std::printf

#include <array> // std::array
#include <queue> // std::queue
#include <string> // std::to_string

using namespace std;

constexpr int kMaxNum(400); // 最大棋盘的大小

struct Node {
  int step, x, y; // step存当前点的最短路径
  Node() {
    step = x = y = 0;
  }
  Node(int a, int b, int c) { // 构造函数，方便入队
    step = a;
    x = b;
    y = c;
  }
};

array<array<int, kMaxNum + 5>, kMaxNum + 5> kChessboard; // 棋盘，存最短路径
array<array<int, 2>, 8> kHorseMove = {1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1,
                                      -2, 1, -1, 2}; // 马移动的移动坐标，一共八种移动方式
queue<Node> kBfsQueue; // BFS用的队列，用了STL现成的，减少码量

// BFS函数，board_xsize和board_ysize都是棋盘大小（忘用全局变量了）
void Bfs(int /* board_xsize */, int /* board_ysize */);
// 判断当前点是否出界
bool IsOverstep(int /* board_xsize */, int /* board_ysize */,
                int /* now_x */, int /* now_y */);

int main(void) {
  int horse_x(0), horse_y(0), m(0), n(0);

  // 初始化棋盘
  for (auto iter = kChessboard.begin(); iter != kChessboard.end(); ++iter)
    iter->fill(-1);

  scanf("%d %d %d %d", &n, &m, &horse_x, &horse_y);
  kBfsQueue.push(Node(0, horse_x, horse_y)); // 起点入队
  kChessboard[horse_x][horse_y] = 0; // 初始化起点最短路径
  Bfs(n, m);

  for (int i = 1; i < n + 1; ++i) {
    for (int j = 1; j < m; ++j) {
      printf("%d", kChessboard[i][j]); // 打印当前点最短路径
      for (int k = 0; k < 5 - to_string(kChessboard[i][j]).size(); ++k) // 输出格式化空格
        putchar(' ');
    }
    printf("%d\n", kChessboard[i][m]); // 输出当前行最后一个点
  }

  return 0;
}

void Bfs(int board_xsize, int board_ysize) {
  Node now_point;

  while (!kBfsQueue.empty()) {
    now_point = kBfsQueue.front(); // 取出队头元素
    kBfsQueue.pop(); // 弹出队头元素

    for (int i = 0; i < 8; ++i) { // 分别朝八个方向移动
      int dx(now_point.x + kHorseMove[i][0]), // 获取移动后的x坐标
          dy(now_point.y + kHorseMove[i][1]); // 获取移动后的y坐标

      // 如果没有越界且并没有搜索过
      // 注意：第二点特别重要。如果不判重，不仅得不出正确的结果，而且会陷入死循环
      if (!IsOverstep(board_xsize, board_ysize, dx, dy) &&
          -1 == kChessboard[dx][dy]) {
        kChessboard[dx][dy] = now_point.step + 1; // 子点的最短路径是当前点＋1
        kBfsQueue.push(Node(now_point.step + 1, dx, dy)); // 子点入队
      }
    }
  }
}

bool IsOverstep(int board_xsize, int board_ysize, int now_x, int now_y) {
  if (now_x < 1 || board_xsize < now_x || now_y < 1 || board_ysize < now_y)
    return true;
  else
    return false;
}

写在最后

这道模板题其实并没有什么难的，只要能把BFS学懂，这道题就是水到渠成、手到擒来，建议先去学习BFS相关知识，再回来做这道题，巩固知识。