ABC246E Bishop 2 Solution

更好的阅读体验戳此进入

题面

给定有障碍的网格图，. 为空地，# 为障碍。给定起点终点，每次移动仅可以斜向走任意长度，问从起点到终点的最少移动次数，可能无解，无解输出 -1。

Solution

BFS 较为显然，因为时限 6000ms，只要写的不太丑直接搜也能过。对于本题，使用 01BFS 较为显然。我们在宽搜每次搜一步且距离仅为 $1$$1$，并记录上一步的方向，如果同向则认为走了一个 $0$$0$ 边，异向则为 $1$$1$ 边，开个双端队列，同向插到前面，反之插到后面，按照正常宽搜每次取队头扩展即可。

需要注意对于 01BFS 时，我们判断是否走过和是否为答案的时候，需要在从队头取元素的时候判断，而不是在扩展的时候判断。因为如果在某一次由 $1$$1$ 扩展的时候如果直接把 $vis$$vis$ 设为 $\mathtt{\text{true}}$$\texttt{true}$，但是这可能会导致后面从 $0$$0$ 扩展的，本应能插在队列中比这个更前面的更优的无法转移，使答案更劣。同时我们也需要考虑到不同方向的时候扩展也是不同，所以 $vis$$vis$ 中也要考虑到方向这一维。

Code

xxxxxxxxxx
91
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define CHK(x, y) (x >= 1 && x <= N && y >= 1 && y <= N && !mp[x][y])
24

25
template<typename T = int>
26
inline T read(void);
27

28
int N;
29
int dx[10] = {0,  -1, -1, 1, 1};
30
int dy[10] = {0,  -1, 1, -1, 1};
31
int vis[1600][1600][5];
32
bool mp[1600][1600];
33

34
struct Status{
35
    int x, y;
36
    int dir;//direction 1, 2, 3, 4
37
    int dist;
38
}S, T;
39
void 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
}
47
void 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

66
int 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

77
template<typename T>
78
inline 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
}

UPD

update-2022_10_21 初稿