洛谷 P1443 马的遍历题解

题目链接：https://www.luogu.org/problem/P1443

题目描述

有一个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    

---

题解

此题是典型的BFS问题。不过和01迷宫问题有两点不同：一是马的走法不是上下左右，所以pos数组需要修改，二是走的步数需要从队列中元素的步数加1。还有一个小问题就是要控制cout的输出格式，刚开始没有注意，10个全WA了。

 #include <iostream>

 #include <stdio.h>

 #include <math.h>

 #include <algorithm>

 #include <string.h>

 using namespace std;

 struct Node

 {

     int x, y;

     int step;

 };

 Node q[];

 const int MAXN = ;

 int n, m, a, b, c, d, step, front, rear, ans[MAXN][MAXN];

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

 bool vis[MAXN][MAXN];

 void bfs()

 {

     Node now, next;

     now.x = a;

     now.y = b;

     vis[a][b] = ;

     now.step = ;

     front = rear = ;

     q[rear] = now;

     rear++;

     while(front < rear)

     {

         now = q[front++];

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

         {

             int nx = now.x + pos[i][];

             int ny = now.y + pos[i][];

             if(nx <= n && nx >  && ny <= m && ny >

                 && vis[nx][ny] == false)

             {

                 vis[nx][ny] = true;

                 q[rear].x = nx;

                 q[rear].y = ny;

                 q[rear].step = now.step + ;

                 ans[nx][ny] = q[rear].step;

                 rear++;

             }

         }

     }

 }

 int main()

 {

     cin >> n >> m >> a >> b;

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

     {

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

         {

             ans[i][j] = -;

         }

     }

     ans[a][b] = ;

     step = ;

     bfs();

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

     {

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

         {

             cout.width();

             cout.setf(ios::left);

             cout << ans[i][j];

         }

         cout << endl;

     }

     return ;

 }