Submission #1174084

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
    int a[450], b[450], c[450], d[450];
    int h, w, k, t;
    cin >> h >> w >> k >> t;
    for (int i = 0; i < k; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--; b[i]--; c[i]--; d[i]--;
    }

    int p[30][30];
    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            p[y][x] = -1;
        }
    }
    for (int i = 0; i < k; i++) {
        p[a[i]][b[i]] = i;
    }

    char *ss = new char[451 * t + 1];
    mt19937_64 mt;

    for (int l = 0; l < t; l++) {
        char *s = ss + 451 * l;
        int u[450] = {}, n = 0;
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                int i = p[y][x];
                if (i < 0) continue;
                int dy = c[i] - y;
                int dx = d[i] - x;
                int m = 0b0000; // UDLR
                //if (mt() % 256 < max(1 - l, 0)) m = mt() & 0b1111;
                if (dy < 0) m |= 0b1000;
                if (dy > 0) m |= 0b0100;
                if (dx < 0) m |= 0b0010;
                if (dx > 0) m |= 0b0001;
                if (y ==     0 || p[y - 1][x] != -1) m &= 0b0111;
                if (y == h - 1 || p[y + 1][x] != -1) m &= 0b1011;
                if (x ==     0 || p[y][x - 1] != -1) m &= 0b1101;
                if (x == w - 1 || p[y][x + 1] != -1) m &= 0b1110;
                if (m == 0) {
                    s[i] = '-';
                } else {
                    int z[4];
                    z[0] = (y < 5) - (y >= 25);
                    z[1] = -z[0];
                    z[2] = (x < 5) - (x >= 25);
                    z[3] = -z[2];
                    int j0 = mt() % 4, j2, js = -10;
                    for (int j = 0; j < 4; j++) {
                        int j1 = (j + j0) % 4;
                        int jt = z[j1];
                        if ((m >> j1 & 1) && jt > js) {
                            j2 = j1;
                            js = jt;
                        }
                    }
                    s[i] = "RLDU"[j2];
                    switch (s[i]) {
                    case 'R': p[y][x + 1] = -2; break;
                    case 'L': p[y][x - 1] = -2; break;
                    case 'D': p[y + 1][x] = -2; break;
                    case 'U': p[y - 1][x] = -2; break;
                    }
                }
            }
        }
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                int i = p[y][x];
                if (i < 0 || u[i] || s[i] == '-') continue;
                switch (s[i]) {
                case 'R': p[y][x + 1] = i; break;
                case 'L': p[y][x - 1] = i; break;
                case 'D': p[y + 1][x] = i; break;
                case 'U': p[y - 1][x] = i; break;
                }
                p[y][x] = -1;
                u[i] = 1;
                n++;
            }
        }

        //for (int i = 0; i < k; i++) {
        //    cout << (int)s[i] << " ";
        //}
        //cout << endl;
        s[k] = '\n';
        if (n <= 1) {
            ss[l * 451] = 0;
            cout << l << '\n' << ss;
            cout << flush;
            break;
        }
    }

    return 0;
}

Submission Info

Judge Result