文章目录
简单的BFS模板题，开始我是做个N*M次BFS求起始点到终止点的次数，导致超时。结果发现一次BFS就可以搞定。
题目描述
有一个n*m的棋盘
(1
<n,m
<=400
)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入格式
一行四个数据，棋盘的大小和马的坐标
输出格式
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define MAX 400
using namespace std
;
int dx
[] = {2, -2, 2, -2, -1, 1, -1, 1}, dy
[] = {1, 1, -1, -1, 2, 2, -2, -2};
struct Node
{
int x
;
int y
;
int Step
;
};
queue
<Node
> q
;
int N
, M
, SX
, SY
;
int vis
[MAX
][MAX
];
int result
[MAX
][MAX
];
void BFS() {
Node cur
;
cur
.x
= SX
;
cur
.y
= SY
;
cur
.Step
= 0;
vis
[SX
][SY
] = 1;
q
.push(cur
);
while (!q
.empty()) {
Node point
= q
.front();
q
.pop();
for (int i
= 0; i
< 8; ++i
) {
int nx
= point
.x
+ dx
[i
];
int ny
= point
.y
+ dy
[i
];
if (nx
< 1 || nx
> N
|| ny
< 1 || ny
> M
|| vis
[nx
][ny
] == 1)
continue;
vis
[nx
][ny
] = 1;
Node next
;
next
.x
= nx
;
next
.y
= ny
;
next
.Step
= point
.Step
+ 1;
result
[next
.x
][next
.y
] = next
.Step
;
q
.push(next
);
}
}
}
int main() {
cin
>> N
>> M
;
cin
>> SX
>> SY
;
BFS();
for (int i
= 1; i
<= N
; ++i
) {
for (int j
= 1; j
<= M
; ++j
) {
if (i
== SX
&& j
== SY
)
printf("%-5d", 0);
else if (!result
[i
][j
])
printf("%-5d", -1);
else
printf("%-5d", result
[i
][j
]);
}
cout
<< endl
;
}
}
