洛谷 P1443 马的遍历
题目描述
有一个nm的棋盘(1<n,m<=400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输出格式
一个nm的矩阵,代表马到达某个点最少要走几步(左对齐,宽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");
}
}
下面是手动模拟样例:
有错误欢迎各位大佬纠正!