ABC246E Bishop 2 Solution

• ABC246E Bishop 2 Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

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

Solution

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

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

int N;
int dx[10] = {0,  -1, -1, 1, 1};
int dy[10] = {0,  -1, 1, -1, 1};
int vis[1600][1600][5];
bool mp[1600][1600];

struct Status{
    int x, y;
    int dir;//direction 1, 2, 3, 4
    int dist;
}S, T;
void Init(void){
    char c = getchar();
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j){
        while(c != '.' && c != '#')c = getchar();
        mp[i][j] = c == '.' ? false : true;
        c = getchar();
    }
}
void bfs(void){
    deque < Status > dq;
    dq.push_back(S);
    while(!dq.empty()){
        auto tp = dq.front(); dq.pop_front();
        if(vis[tp.x][tp.y][tp.dir])continue;
        vis[tp.x][tp.y][tp.dir] = true;
        if(tp.x == T.x && tp.y == T.y)
            printf("%d\n", tp.dist), exit(0);
        // printf("Current pos (%d, %d): dis = %d, dir = %d\n", tp.x, tp.y, tp.dist, tp.dir);
        for(int i = 1; i <= 4; ++i){
            int tx = tp.x + dx[i], ty = tp.y + dy[i];
            if(!CHK(tx, ty))continue;
            if(i == tp.dir)dq.push_front(Status{tx, ty, i, tp.dist});
            else dq.push_back(Status{tx, ty, i, tp.dist + 1});
        }
    }printf("-1\n");
}

int main(){
    // freopen("test_11.txt", "r", stdin);
    N = read();
    int x = read(), y = read(); S = Status{x, y, 0, 0};
    x = read(), y = read(); T = Status{x, y, 0, 0};
    Init();
    bfs();
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template<typename T>
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_10_21 初稿