Submission #1173518

---

Source Code Expand

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

const int INF = 1145141919;

const char U = 'U';
const char D = 'D';
const char L = 'L';
const char R = 'R';
const char NONE = '-';
const char moves[5] = {U, D, L, R, NONE};

// U, D, L, R, N
const int dx[5] = {0, 0, -1, 1, 0};
const int dy[5] = {-1, 1, 0, 0, 0};

int field_height;
int field_width;
int num_car;
int max_output;

vector<string> commands;

struct Car {
    int x;
    int y;
    int tx;
    int ty;
    Car (int x=0, int y=0, int tx=0, int ty=0) {
        this->x = x;
        this->y = y;
        this->tx = tx;
        this->ty = ty;
    }
};

Car cars[450];

void input() {
    cin >> field_height >> field_width >> num_car >> max_output; cin.ignore();
    for (int i = 0; i < num_car; i++) {
        cin >> cars[i].y >> cars[i].x >> cars[i].ty >> cars[i].tx; cin.ignore();
    }
}

double evaluate(int num_output) {
    double pd = 20;
    for (int i = 0; i < num_car; i++) {
        pd += abs(cars[i].x - cars[i].tx) + abs(cars[i].y - cars[i].ty);
    }

    double pt = 10 + num_output*0.01;
    return 10000000 / (pd + pt);
}

bool in_range(int x, int y) {
    return 0 <= x && x < field_width && 0 <= y && y < field_height;
}

int distance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

void think() {


    for (int t = 0; t < max_output; t++) {
        Car pre_cars[450];
        memcpy(&pre_cars, &cars, sizeof(cars));

        bool is_car_this_turn[30][30] = {};
        bool is_car_next_turn[30][30] = {};

        for (int i = 0; i < num_car; i++) {
            is_car_this_turn[cars[i].y][cars[i].x] = true;
        }

        string movement;
        for (int i = 0; i < num_car; i++) {
            movement.push_back(NONE);
        }

        bool is_action = false;
        for (int i = 0; i < num_car; i++) {
            int min_dist = distance(cars[i].x, cars[i].y, cars[i].tx, cars[i].ty);
            int dir = 4;
            for (int d = 0; d < 5; d++) {
                int nx = cars[i].x + dx[d];
                int ny = cars[i].y + dy[d];

                if (!in_range(nx, ny)) continue;
                if (is_car_this_turn[ny][nx]) continue;
                if (is_car_next_turn[ny][nx]) continue;

                int dist = distance(nx, ny, cars[i].tx, cars[i].ty);
                if (dist < min_dist) {
                    min_dist = dist;
                    dir = d;
                }
            }
            if (moves[dir] != NONE) is_action = true;

            int nx = cars[i].x + dx[dir];
            int ny = cars[i].y + dy[dir];
            cars[i].x = nx;
            cars[i].y = ny;
            is_car_next_turn[ny][nx] = true;
            movement[i] = moves[dir];
        }
        if (!is_action) break;
        commands.push_back(movement);
    }
}

void output() {
    cout << commands.size() << endl;
    for (int t = 0; t < commands.size(); t++) {
        cout << commands[t] << endl;
    }
}

int main () {
    input();
    think();
    output();
    // cerr << evaluate(commands.size()) << endl;
}

Submission Info

Judge Result