【洛谷】P1443 马的遍历

题目：https://www.luogu.org/problemnew/show/P1443

简单的BFS模板题——因为我写出来了。

分析过程：

n*m矩阵，用二维数组

数据不大，二维数组稳了

先把二维数组初始化为-1，马的坐标，即起点的坐标再设为0

接着开始遍历——8个方向（下过中国象棋的大牛应该不陌生）

设一个结构，储存落点的位置与所走的步数，每走一次就记录一次

此时，还要判断落点是否还是-1，这样就可以避免重复

本来这样就可以AC了，但此题有个陷阱就是：

输出格式：

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

所以，要在输出上花点心思......（其实是要注意审题）

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<queue>

 #define MAXN 402

 using namespace std;

 int ans[MAXN][MAXN];

 int n, m, n_b, m_b;

 int run_x[] = { , , , , -, -, -, - };

 int run_y[] = { , -, , -, , -, , - };

 struct node{

     int x, y;

     int step;

 };

 queue<node> q;

 void bfs(){

     node a;

     a.x = n_b;

     a.y = m_b;

     a.step = ;

     ans[a.x][a.y] = a.step;

     q.push(a);

     while(!q.empty()){

         node b = q.front();

         node c;

         q.pop();

         for(int i = ; i < ; i++){

             c.x = b.x + run_x[i];

             c.y = b.y + run_y[i];

             if( < c.x && c.x <= n &&  < c.y && c.y <= m

     && ans[c.x][c.y] == -){

                 c.step = b.step + ;

                 ans[c.x][c.y] = c.step;

                 q.push(c);

             }

         }

     }

 }

 int main()

 {

     while(cin >> n >> m >> n_b >> m_b){

         memset(ans, -, sizeof(ans));

         bfs();

         for(int i = ; i <= n; i++){

             for(int j = ; j <= m; j++){

                 printf("%-5d", ans[i][j]);

             }

             cout << endl;

         }

     }

     return ;

 }

下面说说我对BFS的理解

BFS与DFS有个很相似的地方：对于所有情况，它们都做着相同的行为来遍历完所有情况。

所以，BFS里肯定有一个“核心循环”（这里指对于每个方法路径的遍历），然后再判断下一位置是否还满足条件。

如：

for(int i = ; i < ; i++){

            c.x = b.x + run_x[i];

            c.y = b.y + run_y[i];

            if( < c.x && c.x <= n &&  < c.y && c.y <= m 
　　　　　　&& ans[c.x][c.y] == -){

                c.step = b.step + ;

                ans[c.x][c.y] = c.step;

                q.push(c);

            }

        }

这里的循环是对马的8个方向的遍历，接着if语句是判断马跳下一步后是否还在棋盘上或者是否已经来过。

虽然我做过的题不多，但做过的题都有这种“核心循环”，所以就特意画出来做了个笔记。

嘻嘻，说了这么多好像还云里雾里的感觉。

不知是不是，感觉学习算法还是要抓住那类算法的特性去理解，这样学起来就会更轻松。

有点理解师兄所说的：只要思维理解了，代码的实现就不是问题了。

巴特西

【洛谷】P1443 马的遍历

最新文章

热门文章