@[Algorithm_ZRF](/user/1044048) bfs 没返回值。
by xiaoshumiao @ 2024-01-29 21:32:26
@[xiaoshumiao](/user/1008513) 返回了啊
```cpp
if (now.x == 1 && now.y == 1) return now.cnt;
```
by Algorithm_ZRF @ 2024-01-30 07:59:33
@[xiaoshumiao](/user/1008513) 我改了一下,20tps了
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 25;
int dx[12] = {1, -1, 2, -2, 1, -1, 2, -2, 2, -2, -2, 2};
int dy[12] = {2, 2, 1, 1, -2, -2, -1, -1, 2, 2, -2, -2};
int x3, y3, x2, y2;
bool chess[maxn][maxn];
struct ss {
int x, y, cnt;
};
queue<ss> q;
void Read() {
cin >> x3 >> y3;
cin >> x2 >> y2;
}
int bfs(int x, int y, 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 == 1 && now.y == 1)
return now.cnt;
for (int i = 0; i < 12; ++i) {
int tx = now.x + dx[i];
int ty = now.y + dy[i];
ss k;
k.x = tx;
k.y = ty;
k.cnt = now.cnt + 1;
if (tx <= 0 || ty <= 0)continue; //判断边界
if (chess[tx][ty])continue; //去重
chess[tx][ty] = 1;
q.push(k);
}
}
}
void Solve() {
Read();
cout << bfs(x3, y3, 0) << endl;
while (!q.empty()) {
q.pop();
}
for (int i = 1; i <= maxn; ++i) {
for (int j = 1; j <= maxn; ++j) {
chess[i][j] = 0;
}
}
cout << bfs(x2, y2, 0) << endl;
}
int main() {
Solve();
exit(0);
}
```
#10RE,#1,#7AC,其余WA
by Algorithm_ZRF @ 2024-01-30 09:06:23
注意到36行,这里判断边界只考虑了上边界和左边界,事实上也有可能超下边界和右边界,即tx>24||ty>24,超过就会造成RE(毕竟chess数组只开到了24*24),所以改为:
```cpp
if (tx <= 0 || ty <= 0 || tx >= 25 || ty >= 25)continue; //判断边界
```
再看50、51行,清零的时候数组越界了,chess的最大下标实际上只有chess[MAXN-1][MAXN-1](因为还有一个chess[0][0]),所以循环要改成:
```cpp
for (int i = 1; i < maxn; ++i) {
for (int j = 1; j < maxn; ++j) {
chess[i][j] = 0;
}
}
```
亲测有效(https://www.luogu.com.cn/record/146555536)
by LH4432 @ 2024-02-08 18:51:47