洛谷刷题记——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相关知识,再回来做这道题,巩固知识。

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

返回顶部
京ICP备15050995号