SnackOI R1-C 山峰之上 题解

· · 个人记录

闲话

这题太吃操作了。

n 较小的部分分

非常直观啊，可以直接设 dis_{i,j,k,0/1/2} 表示当前在 {i,j}，第 k 个月，在水里泡了 0/1/2 月，最少的步数。

我们考虑 dijkstra，每次遍历到一个 i,j,k,0/1/2 就进行转移。转移分为两种，移动和不移动。细节稍微有点多。需要注意的是，如果当前第四个数是 2，那么不能走到河里。期望得分 44pts，实际上可以获得更高的分数。

特殊性质

特殊性质 BCD，直接输出 2n - 1，期望得分 48pts。

特殊性质 BD，直接跑 bfs，期望得分 52pts。

特殊性质 B，发现月份这一维就没啥用了，直接把这一维弄掉，跑 dij，期望得分 64pts。

特殊性质 D，可以直接 bfs，因为边权全都是 1 了。期望得分 76pts。

特殊性质 A 和 C 可以让你减少一点点码量，但是基本没啥用（（（

正解

01bfs。处理边权为 0 或 1 的图。

具体地，开一个 deque，如果边权是 0，就把这个元素插入前面，否则插入后面。这样也可以保持 dis 递增的原则。期望得分 100pts。

献上代码。

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

const int N = 1010;
const int M = 13;
const int K = 3;

const int INF = 1e9;

int d[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

struct V {
    int x, y;   
};

struct node {
    int x, y, month, water; 
};

int ans;

int n, m, z;
int l[N][N], r[N][N];

int dis[N][N][M][K];

bool vis[N][N][M][K];

char a[N][N];

std::deque <node> q;
std::pair <int, int> river[N * N];

bool check (int x, int y, int mon) {
    if (l[x][y] <= r[x][y]) {
        return (mon >= l[x][y] && mon <= r[x][y]);
    }
    return (mon >= l[x][y] || mon <= r[x][y]);
}

int next_month (int x) {
    if (x == 12) {
        return 1;
    }
    return x + 1;
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("peak25.in", "r", stdin);
        freopen("peak25.out", "w", stdout);
    #endif
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr); 

    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            std::cin >> a[i][j];

            if (a[i][j] == 'R') {
                river[z++] = {i, j};
            }
        }
    }
    for (int i = 1; i <= z; ++i) {
        std::cin >> l[river[i - 1].first][river[i - 1].second] >> r[river[i - 1].first][river[i - 1].second];
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = 1; k <= 12; ++k) {
                for (int l = 0; l <= 2; ++l) {
                    dis[i][j][k][l] = INF;
                }
            }
        }
    }
    dis[1][1][1][0] = 1;
    q.push_back((node){1, 1, 1, 0});

    while (!q.empty()) {
        node now = q.front();
        q.pop_front();

        int nx = now.x, ny = now.y, nm = now.month, nw = now.water;

        if (vis[nx][ny][nm][nw]) {
            continue;
        }
        vis[nx][ny][nm][nw] = 1;
        //std::cout << "F:" << nx << ' ' << ny << ' ' << nm << ' ' << nw << std::endl;

        //stay
        int tm = next_month(nm);
        if (a[nx][ny] == 'R' && !check(nx, ny, next_month(nm))) {
            if (nw < 2 && dis[nx][ny][nm][nw] + 1 < dis[nx][ny][tm][nw + 1]) {
                dis[nx][ny][tm][nw + 1] = dis[nx][ny][nm][nw] + 1;
                q.push_back((node){nx, ny, tm, nw + 1});
            }
        } else {
            if (dis[nx][ny][nm][nw] + 1 < dis[nx][ny][tm][0]) {
                dis[nx][ny][tm][0] = dis[nx][ny][nm][nw] + 1;
                q.push_back((node){nx, ny, tm, 0});
            }
        }

        //move
        for (int f = 0; f < 4; ++f) {
            int tx = nx + d[f][0], ty = ny + d[f][1];
            if (tx && ty && tx <= n && ty <= m && a[tx][ty] != '#') {
                int add = 0, tm = nm;
                if (a[nx][ny] != 'N') {
                    add = 1, tm = next_month(nm);
                }

                if (a[tx][ty] == 'R' && !check(tx, ty, tm)) {
                    if (nw >= 2) {
                        continue;
                    }
                    if (dis[nx][ny][nm][nw] + add < dis[tx][ty][tm][nw + 1]) {
                        dis[tx][ty][tm][nw + 1] = dis[nx][ny][nm][nw] + add;
                        if (add) {
                            q.push_back((node){tx, ty, tm, nw + 1});
                        } else {
                            q.push_front((node){tx, ty, tm, nw + 1});
                        }
                    }
                } else {
                    if (dis[nx][ny][nm][nw] + add < dis[tx][ty][tm][0]) {
                        dis[tx][ty][tm][0] = dis[nx][ny][nm][nw] + add;
                        if (add) {
                            q.push_back((node){tx, ty, tm, 0});
                        } else {
                            q.push_front((node){tx, ty, tm, 0});
                        }
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            ans = INF;
            for (int k = 1; k <= 12; ++k) {
                for (int l = 0; l <= 2; ++l) {
                    ans = std::min(ans, dis[i][j][k][l]);
                }
            }
            if (ans == INF) {
                //std::cout << "0 ";
                continue;
            }
            //std::cout << ans << ' ';
        }
        //std::cout << std::endl;
    }

    ans = INF;
    for (int k = 1; k <= 12; ++k) {
        for (int l = 0; l <= 2; ++l) {
            ans = std::min(ans, dis[n][m][k][l]);
        }
    }
    if (ans == INF) {
        std::cout << -1;
    } else {
        std::cout << ans;
    }

    return 0;
}