返回题解分享
讨论 / 题解分享/ 帖子详情

出租车(编程题) - 题解

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int ret = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
    for (; isdigit(ch); ch = getchar()) ret = ret * 10 + ch - 48;
    return ret * f;
}

const int maxn = 105;
const int xx[4] = { -1, 0, 1, 0 };
const int yy[4] = { 0, 1, 0, -1 };
const double INF = 10000000000005ll;

bool vis[maxn][maxn][4];
double T = 0, dis[maxn][maxn][4];
struct node { int x, y, f; } a[6];
inline bool operator ==(node a, node b) { return a.x == b.x && a.y == b.y; }

struct Node { double d; node x; };
inline bool operator <(Node a, Node b) { return a.d < b.d; }
inline bool operator >(Node a, Node b) { return a.d > b.d; }

int N, M, Q, h[maxn], w[maxn], g[maxn][maxn], r[maxn][maxn];

inline double wait(node u, double tim) {
    tim += T;
    tim -= floor(tim / (g[u.x][u.y] + r[u.x][u.y])) * (g[u.x][u.y] + r[u.x][u.y]);
    if (u.f & 1) { // 东西向 初始红
        if (abs(tim - g[u.x][u.y]) < 1e-6) return 0;
        if (tim > g[u.x][u.y]) return 0;
        else return g[u.x][u.y] - tim;
    }
    else {
        if (abs(tim - g[u.x][u.y]) < 1e-6) return r[u.x][u.y];
        if (tim < g[u.x][u.y]) return 0;
        else return r[u.x][u.y] + g[u.x][u.y] - tim;
    }
}

inline double getDistance(node a, node b) {
    return (a.x == b.x) ? abs(w[a.y] - w[b.y]) : abs(h[a.x] - h[b.x]);
}

double Calc() {
    if (a[0] == a[2] && a[1] == a[3]) return 0;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            for (int k = 0; k < 4; ++k) {
                dis[i][j][k] = INF;
                vis[i][j][k] = 0;
            }
    a[1].f = (a[0].x == a[1].x) ? ( (a[1].y > a[0].y) ? 3 : 1 ) : ( (a[1].x > a[0].x) ? 0 : 2 );
    dis[a[1].x][a[1].y][a[1].f] = getDistance(a[0], a[1]) * 0.5;
    priority_queue < Node, vector<Node>, greater<Node> > Q;
    Node fuck; // 因为官网的c++不支持 Q.push({ dis[a[1].x][a[1].y][a[1].f], a[1] });
    //所以临时改的,言辞比较激烈
    fuck.d = dis[a[1].x][a[1].y][a[1].f];
    fuck.x = a[1];
    Q.push(fuck);
    while (!Q.empty()) {
        node u = Q.top().x, v;
        Q.pop();
        if (vis[u.x][u.y][u.f]) continue;
        vis[u.x][u.y][u.f] = 1;
        // 掉头
        v.x = u.x + xx[u.f], v.y = u.y + yy[u.f], v.f = (u.f + 2) % 4;
        if (v.x >= 1 && v.x <= N && v.y >= 1 && v.y <= M) {
            if (dis[v.x][v.y][v.f] > dis[u.x][u.y][u.f] + getDistance(u, v)) {
                dis[v.x][v.y][v.f] = dis[u.x][u.y][u.f] + getDistance(u, v);
                fuck.d = dis[v.x][v.y][v.f];
                fuck.x = v;
                Q.push(fuck);
            }
        }
        // 右转
        v.x = u.x + xx[(u.f + 3) % 4], v.y = u.y + yy[(u.f + 3) % 4], v.f = (u.f + 1) % 4;
        if (v.x >= 1 && v.x <= N && v.y >= 1 && v.y <= M) {
            if (dis[v.x][v.y][v.f] > dis[u.x][u.y][u.f] + getDistance(u, v)) {
                dis[v.x][v.y][v.f] = dis[u.x][u.y][u.f] + getDistance(u, v);
                fuck.d = dis[v.x][v.y][v.f];
                fuck.x = v;
                Q.push(fuck);
            }
        }
        // 左转
        double t = wait(u, dis[u.x][u.y][u.f]);
        v.x = u.x + xx[(u.f + 1) % 4], v.y = u.y + yy[(u.f + 1) % 4], v.f = (u.f + 3) % 4;
        if (v.x >= 1 && v.x <= N && v.y >= 1 && v.y <= M) {
            if (dis[v.x][v.y][v.f] > dis[u.x][u.y][u.f] + getDistance(u, v) + t) {
                dis[v.x][v.y][v.f] = dis[u.x][u.y][u.f] + getDistance(u, v) + t;
                fuck.d = dis[v.x][v.y][v.f];
                fuck.x = v;
                Q.push(fuck);
            }
        }
        // 直行
        t = wait(u, dis[u.x][u.y][u.f]);
        v.x = u.x + xx[(u.f + 2) % 4], v.y = u.y + yy[(u.f + 2) % 4], v.f = u.f;
        if (v.x >= 1 && v.x <= N && v.y >= 1 && v.y <= M) {
            if (dis[v.x][v.y][v.f] > dis[u.x][u.y][u.f] + getDistance(u, v) + t) {
                dis[v.x][v.y][v.f] = dis[u.x][u.y][u.f] + getDistance(u, v) + t;
                fuck.d = dis[v.x][v.y][v.f];
                fuck.x = v;
                Q.push(fuck);
            }
        }
    }
    a[3].f = (a[2].x == a[3].x) ? ( (a[3].y > a[2].y) ? 3 : 1 ) : ( (a[3].x > a[2].x) ? 0 : 2 );
    return dis[a[3].x][a[3].y][a[3].f] - getDistance(a[2], a[3]) * 0.5;
}

int main() {
    N = read(), M = read();
    for (int i = 2; i <= N; ++i) h[i] = read();
    for (int i = 2; i <= M; ++i) w[i] = read();
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j) g[i][j] = read();
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j) r[i][j] = read();
    a[0].x = read(), a[0].y = read(), a[1].x = read(), a[1].y = read();
    a[4] = a[0], a[5] = a[1];
    for (Q = read(); Q--; ) {
        a[2].x = read(), a[2].y = read();
        a[3].x = read(), a[3].y = read();
        T += Calc();
        a[0] = a[2], a[1] = a[3];
        a[2].x = read(), a[2].y = read();
        a[3].x = read(), a[3].y = read();
        T += Calc();
        a[0] = a[2], a[1] = a[3];
    }
    a[2] = a[4], a[3] = a[5];
    T += Calc();
    printf("%.1lf", T);
    return 0;
}
0 回复 0 转发 0 喜欢 1 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!