Submission #2084055

---

Source Code Expand

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

#define int long long

int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int H, W, K, sr, sc;
int s[50][50] = {};
int d[50][50] = {};
bitset<50> visited[50] = {};
char ans[4] = {'R', 'D', 'L', 'U'};

unsigned randxor() {
    static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned t;
    t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

int rand_dist(int max) {
    return randxor() % max;
}

void sqcpy(bitset<50> parent[50], bitset<50> child[50]) {
    for (int i = 0; i < 50; i++) {
        child[i] = parent[i];
    }
}

int evaluate(bitset<50> vsd[50], int turn, int x, int y) {
    int res = 0;
    for (int i = turn; i < min(turn + 40, K); i++) {
        if (!vsd[y][x]) {
            res += s[y][x] - i * d[y][x];
            vsd[y].set(x);
        }
        vector<int> way;
        for (int j = 0; j < 4; j++) {
            if (s[y + dy[j]][x + dx[j]] != -1) {
                way.push_back(j);
            }
        }
        int det = rand_dist(way.size());
        x += dx[way[det]], y += dy[way[det]];
    }
    return res;
}

int determine_hand(bitset<50> vsd[50], int turn, int x, int y) {
    int hand;
    int max_score = LLONG_MIN;
    vector<int> way;
    for (int i = 0; i < 4; i++) {
        if (s[y + dy[i]][x + dx[i]] == -1) {
            continue;
        }
        way.push_back(i);
        int cur_score = 0;
        for (int j = 0; j < 200; j++) {
            bitset<50> vsd_cpy[50];
            sqcpy(vsd, vsd_cpy);
            cur_score += evaluate(vsd_cpy, turn, x + dx[i], y + dy[i]);
        }
        if (cur_score > max_score) {
            max_score = cur_score;
            hand = i;
        }
    }
    return hand;
}

signed main() {
    cin >> H >> W >> K >> sr >> sc;
    for (int i = 0; i < 50; i++) {
        string a;
        cin >> a;
        for (int j = 0; j < 50; j++) {
            if (a[j] == '#') {
                s[i][j] = -1;
            }
        }
    }
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int fr, fc, F, D;
        cin >> fr >> fc >> F >> D;
        s[fr - 1][fc - 1] = F;
        d[fr - 1][fc - 1] = D;
    }
    sr--, sc--;
    for (int i = 0; i < K; i++) {
        int hand = determine_hand(visited, i, sc, sr);
        cout << ans[hand];
        sc += dx[hand], sr += dy[hand];
        visited[sr].set(sc);
    }
    cout << endl;
    return 0;
}

Submission Info

Judge Result