洛谷 P1443 马的遍历

洛谷 P1443 马的遍历

题目链接

题目描述
有一个nm的棋盘(1<n,m<=400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输出格式
一个n
m的矩阵,代表马到达某个点最少要走几步(左对齐,宽5格,不能到达则输出-1)
输入
3 3 1 1
输出
0 3 2
3 -1 1
2 1 4
**题解:**赤裸裸的广搜和STL的结合,第一步读入棋盘长宽和马的初始坐标,把马的初始坐标压入队尾,设置两个数组,ans和vis,ans用来记录步数,vis用来标记该坐标是否被访问过,如果不标记的话会死循环,然后开始bfs,在队列不为空时,对首元素进行拓展(8个方向,for循环),将拓展的元素压入队尾,首元素出队,重复操作
一定要记得标记数组和首元素出队,不然都会造成死循环
听大佬说可以用pair,这样就不用两个队列了,可惜我现在还不会hhh
AC代码:

#include<bits/stdc++.h>
using namespace std;
int n, m, a[500][500];
queue<int> q, q1;
int dx[8] = {2, 2, 1, 1, -1, -1, -2, -2}; //马走日的八个方向
int dy[8] = {1, -1, -2, 2, 2, -2, 1, -1};
int ans[500][500];
int vis[500][500];
int main() {
 memset(ans, -1, sizeof(ans));//初始化为-1,正好也解决了题目说不能到达则输出-1 
 int n, m, startx, starty;
 cin >> n >> m >> startx >> starty;
 q.push(startx);
 q1.push(starty);//马的初坐标入队列
 ans[startx][starty] = 0;//记录步数
 vis[startx][starty] = 1;//标记数组,看这个点是否被访问过
  while (!q.empty()) {
  for (int i = 0; i < 8; i++) {
   int tx = q.front() + dx[i];
   int ty = q1.front() + dy[i];
   if (tx > 0 && tx <= n && ty > 0 && ty <= m && vis[tx][ty] == 0) {
   vis[tx][ty] = 1;
    ans[tx][ty] = ans[q.front()][q1.front()] + 1;
    q.push(tx);
    q1.push(ty);
       }
  }
  q.pop();
  q1.pop();
 }
 for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
   printf("%-5d", ans[i][j]);
  }
  printf("\n");
   }
}

下面是手动模拟样例:
洛谷 P1443 马的遍历

有错误欢迎各位大佬纠正!

上一篇:G - Millionaire Madness(bfs+优先队列)


下一篇:加密与解密 charter 4 学习记录