**在线等急!!!!!!!!!!!!!!!!**
by Wyy_w123 @ 2023-07-10 21:30:13
考虑点 $(x_1, y_1)$ 和 $(x_2, y_2)$。$(x_1, y_1)$ 通过方向一可以达到 $(x_3, y_3)$,类似地,$(x_2, y_2)$ 通过方向二可以达到 $(x_3, y_3)$ 。在这种情况下,你的代码会从 $(x_1, y_1)$ 搜到 $(x_3, y_3)$,更新`ft[x_3][y_3]`,再从 $(x_3, y_3)$ 搜索方向 $2, 3, 4, \dots, 8$。当你的代码从 $(x_2, y_2)$ 搜到 $(x_3, y_3)$ 时,因为你的代码里写着 `k+1<ft[xt][yt]`,而我们说了 $(x_1, y_1)$ 和 $(x_2, y_2)$ 到 $(x_3, y_3)$ 的距离相等,这时你的代码就不会搜索方向 $2$ 了。看到问题了吗?
最优解有可能就是从方向 $2$ 走的。如果看看答案错误的数据点的话,可以发现你的代码的答案总是比标准答案大,就是因为你的代码没从方向 $2$ 搜。
以下是根据你的`DFS`改写的`BFS`。我已经尝试模仿你的风格了,希望对你有帮助。这个代码在[这个提交](https://www.luogu.com.cn/record/130696969)里AC了。
```c++
//帮助同学修改代码,不是抄!!!我已经做出来了!!!
#include <bits/stdc++.h>
using namespace std;
int n , m , t[101][101] , minn = 10000 , ft[101][101][9];
int ex[8] = {0 , 1 , 0 , -1 , 1 , -1 , 1 , -1};
int ey[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};
bool f[101][101][9];
struct node //保存横下标,纵下标和方向
{
int x , y , dir;
};
void bfs()
{
queue<node> q;
for(int i = 0; i < 8; i ++){ //每个方向先放一个
q.push({1, 1, i});
ft[1][1][i] = 0;
f[1][1][i] = 1;
}
while(!q.empty()){
node cur = q.front();
q.pop();
for(int i = 0; i < 8; i ++){ //向每个方向搜索
if(i != cur.dir){ //方向不能和前面一步一样
int xt = cur.x + ex[i] * t[cur.x][cur.y];
int yt = cur.y + ey[i] * t[cur.x][cur.y];
if (xt >= 1 && xt <= n && yt >= 1 && yt <= m && !f[xt][yt][i]){ //根据BFS的性质,不需要判断ft[这一步] < ft[上一步]
q.push({xt, yt, i});
ft[xt][yt][i] = ft[cur.x][cur.y][cur.dir] + 1;
f[xt][yt][i] = 1;
}
}
}
}
}
int main(){
cin >> m >> n;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cin >> t[i][j];
for(int k = 0; k <= 8; k ++) ft[i][j][k] = 10000;
}
}
bfs();
for(int i = 0; i < 8; i ++){
minn = min(minn, ft[n][m][i]);
}
if(minn == 10000) cout << "NEVER";
else cout << minn;
return 0;
}
```
by user12313 @ 2023-10-20 23:32:54