给定有障碍的网格图,.
为空地,#
为障碍。给定起点终点,每次移动仅可以斜向走任意长度,问从起点到终点的最少移动次数,可能无解,无解输出 -1
。
BFS 较为显然,因为时限 6000ms,只要写的不太丑直接搜也能过。对于本题,使用 01BFS 较为显然。我们在宽搜每次搜一步且距离仅为
需要注意对于 01BFS 时,我们判断是否走过和是否为答案的时候,需要在从队头取元素的时候判断,而不是在扩展的时候判断。因为如果在某一次由
xxxxxxxxxx
911
2
3
4
5
6
7
8
9
10
11using namespace std;
12using namespace __gnu_pbds;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template<typename T = int>
26inline T read(void);
27
28int N;
29int dx[10] = {0, -1, -1, 1, 1};
30int dy[10] = {0, -1, 1, -1, 1};
31int vis[1600][1600][5];
32bool mp[1600][1600];
33
34struct Status{
35 int x, y;
36 int dir;//direction 1, 2, 3, 4
37 int dist;
38}S, T;
39void Init(void){
40 char c = getchar();
41 for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j){
42 while(c != '.' && c != '#')c = getchar();
43 mp[i][j] = c == '.' ? false : true;
44 c = getchar();
45 }
46}
47void bfs(void){
48 deque < Status > dq;
49 dq.push_back(S);
50 while(!dq.empty()){
51 auto tp = dq.front(); dq.pop_front();
52 if(vis[tp.x][tp.y][tp.dir])continue;
53 vis[tp.x][tp.y][tp.dir] = true;
54 if(tp.x == T.x && tp.y == T.y)
55 printf("%d\n", tp.dist), exit(0);
56 // printf("Current pos (%d, %d): dis = %d, dir = %d\n", tp.x, tp.y, tp.dist, tp.dir);
57 for(int i = 1; i <= 4; ++i){
58 int tx = tp.x + dx[i], ty = tp.y + dy[i];
59 if(!CHK(tx, ty))continue;
60 if(i == tp.dir)dq.push_front(Status{tx, ty, i, tp.dist});
61 else dq.push_back(Status{tx, ty, i, tp.dist + 1});
62 }
63 }printf("-1\n");
64}
65
66int main(){
67 // freopen("test_11.txt", "r", stdin);
68 N = read();
69 int x = read(), y = read(); S = Status{x, y, 0, 0};
70 x = read(), y = read(); T = Status{x, y, 0, 0};
71 Init();
72 bfs();
73 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
74 return 0;
75}
76
77template<typename T>
78inline T read(void){
79 T ret(0);
80 short flag(1);
81 char c = getchar();
82 while(c != '-' && !isdigit(c))c = getchar();
83 if(c == '-')flag = -1, c = getchar();
84 while(isdigit(c)){
85 ret *= 10;
86 ret += int(c - '0');
87 c = getchar();
88 }
89 ret *= flag;
90 return ret;
91}
update-2022_10_21 初稿