@[鱡舞](/user/183473) 这题dfs不行,得用bfs
by ⚡小林孑⚡ @ 2020-02-20 18:40:29
你不知道一个神奇的东西叫~~波法师~~ **BFS**么???
**$\LaTeX$**(滑稽)
by JackMerryYoung @ 2020-02-20 18:41:50
```
吾有一术,曰“dfs”。是术曰:
吾有一言,曰“Time Out”。
书之。
是术名曰“dfs”。
吾有一术,曰“bfs”。是术曰:
吾有一言,曰“Accept”。
书之。
是术名曰“bfs”。
```
by JackMerryYoung @ 2020-02-20 18:47:41
好吧,窝试试冰法师
by PrincessYR✨~ @ 2020-02-20 18:49:16
试试这个
```cpp
#include<bits/stdc++.h>
using namespace std;
int u[5] = {0 , -1 , 0 , 1 , 0};
int v[5] = {0 , 0 , 1 , 0 , -1};
struct data {
int x , y;
}a[100005];
queue < data > q;
int n , m , A , B , vis[505][505] , step[505][505];
int main () {
scanf ("%d%d%d%d" , &n , &m , &A , &B);
for (int i = 1 ; i <= A ; i++) {
int temp_x , temp_y;
scanf ("%d%d" , &temp_x , &temp_y);
q.push (data {temp_x , temp_y});
vis[temp_x][temp_y] = 1;
}
for (int i = 1 ; i <= B ; i++) {
scanf ("%d%d" , &a[i].x , &a[i].y);
}
while (! q.empty ()) {
int x = q.front ().x , y = q.front ().y;
q.pop ();
for (int i = 1 ; i <= 4 ; i++) {
int x_1 = x + u[i] , y_1 = y + v[i];
if (x_1 >= 1 && x_1 <= n && y_1 >= 1 && y_1 <= m && vis[x_1][y_1] == 0) {
vis[x_1][y_1] = 1;
step[x_1][y_1] = step[x][y] + 1;
q.push (data {x_1 , y_1});
}
}
}
// for (int i = 1 ; i <= n ; i++) {
// for (int j = 1 ; j <= m ; j++) {
// printf ("%d " , step[i][j]);
// }
// printf ("\n");
// }
for (int i = 1 ; i <= B ; i++) {
printf ("%d\n" , step[a[i].x][a[i].y]);
}
return 0;
}
```
by whc2020 @ 2020-02-20 19:02:06
@[whc2020](/user/185756)
**what is this?**
by PrincessYR✨~ @ 2020-02-20 19:04:24
冰法师……
by whc2020 @ 2020-02-20 19:06:12
@[whc2020](/user/185756)
可不可以在我的代码基础上只是稍微改一下
by PrincessYR✨~ @ 2020-02-20 19:10:26
全部代码太不容易消化了
by PrincessYR✨~ @ 2020-02-20 19:11:03
@[whc2020](/user/185756)
十分感谢
by PrincessYR✨~ @ 2020-02-20 19:11:24