感觉您没完全学懂BFS,建议去仔细去研究一下这道题
by Stasis_ @ 2024-01-29 21:50:23
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
int dx[8] = {1, -1, 2, -2, 1, -1, 2, -2};
int dy[8] = {2, 2, 1, 1, -2, -2, -1, -1};
int n, m, x, y;
int chess[maxn][maxn];
struct ss {
int x, y;
int cnt;
};
queue<ss> q;
void Read() {
cin >> n >> m >> x >> y;
}
void bfs(int x, int y) {
memset(chess,0x3f,sizeof(chess));
ss s;//初始值
s.x = x;
s.y = y;
s.cnt = 0;
chess[x][y] = 0;
q.push(s);
while (!q.empty()) {
ss now = q.front();
q.pop();
for(int i = 0; i < 8; ++i) {
int tx = now.x + dx[i], ty = now.y + dy[i];
ss l;
l.x = tx;
l.y = ty;
l.cnt = now.cnt + 1;
if (tx < 1 || ty < 1 || tx > n || ty > m || chess[now.x][now.y]+1>=chess[tx][ty]) continue; //判断数组是否越界
q.push(l), chess[tx][ty]=chess[now.x][now.y]+1;
}
}
}
void Solve(){
Read();
bfs(x,y);
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
if(chess[i][j]>=1e6) chess[i][j] = -1;
}
}
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
printf("%-5d", chess[i][j]);
}
printf("\n");
}
}
int main(){
Solve();
exit(0);
}
by Stasis_ @ 2024-01-29 21:50:51
@[Stasis_](/user/555308) 刚刚把问题解决了，只剩超时了
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
int dx[8] = {1, -1, 2, -2, 1, -1, 2, -2};
int dy[8] = {2, 2, 1, 1, -2, -2, -1, -1};
int n, m, x, y;
bool chess[maxn][maxn];
struct ss {
int x, y;
int cnt;
};
queue<ss> q;
void Read() {
cin >> n >> m >> x >> y;
}
int bfs(int a, int b, int cnt) {
ss s;//初始值
s.x = x;
s.y = y;
s.cnt = cnt;
chess[x][y] = 1;
q.push(s);
while (!q.empty()) {
ss now = q.front();
q.pop();
if (now.x == a && now.y == b) {
return now.cnt;
}
for (int i = 0; i < 8; ++i) {
int tx = now.x + dx[i], ty = now.y + dy[i];
ss l;
l.x = tx;
l.y = ty;
l.cnt = now.cnt + 1;
if (tx <= 0 || ty <= 0)continue; //判断数组是否越界
if (tx > n || ty > m)continue;//判断数组是否越界
if (chess[tx][ty]) continue; //去重
chess[tx][ty] = 1;
q.push(l);
}
}
return -1;
}
void Solve() {
Read();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
printf("%-5d", bfs(i, j, 0));
while (!q.empty()) q.pop();
memset(chess, 0, sizeof(chess));
}
printf("\n");
}
}
int main() {
Solve();
exit(0);
}
```
by Algorithm_ZRF @ 2024-01-30 10:01:30