CF1933F Turtle Mission Robot and the Earthquake

思路

因为石头的数量太多的不好维护，于是我们转化参照物，直接看作人在动。

那么，人向下走相当于向下走两步，向上走相当于不走，向右走相当于向右下走。

然后直接暴力 BFS 一下，算出走到最后一列的时间，然后将终点按照时间找到转化参照物后的位置，取最小值即可。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 1010,inf = 1e9 + 10;
int n,m;
int arr[N][N],vis[N][N];

struct point{
    int x,y;
};

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void bfs(int x,int y){
    queue<point> q;
    vis[x][y] = 0;
    q.push({x,y});
    while (!q.empty()){
        point u = q.front(); q.pop();
        if (!arr[(u.x + 1) % n][u.y] && !arr[(u.x + 2) % n][u.y]){
            int tx = (u.x + 2) % n,ty = u.y;
            if (!~vis[tx][ty]){
                vis[tx][ty] = vis[u.x][u.y] + 1;
                q.push({tx,ty});
            }
        }
        if (u.y + 1 < m && !arr[(u.x + 1) % n][u.y + 1]){
            int tx = (u.x + 1) % n,ty = u.y + 1;
            if (!~vis[tx][ty]){
                vis[tx][ty] = vis[u.x][u.y] + 1;
                q.push({tx,ty});
            }
        }
    }
}

inline int calc(int x,int tim){
    if (!~tim) return inf;
    int y = (n - 1 + tim) % n;
    return tim + min((x - y + n) % n,(y - x + n) % n);
}

inline void solve(){
    int ans = inf;
    n = read(),m = read();
    for (re int i = 0;i < n;i++){
        for (re int j = 0;j < m;j++){
            vis[i][j] = -1; arr[i][j] = read();
        }
    }
    bfs(0,0);
    for (re int i = 0;i < n;i++) ans = min(ans,calc(i,vis[i][m - 1]));
    if (ans >= inf) puts("-1");
    else printf("%d\n",ans);
}

int main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}