これすき

Advent Calendar Contest Advent Calendarの時の問題っぽい

solution

盤面が$20 \times 20 = 400$マスに対し、実行可能なのが30000,40000stepsぐらいとのことなので、適当にやればできる。

implementation

  • ゴールが見えたら走る
  • 現在位置からまだ眺めたことのない方向があれば回転
  • そうでなければ、現在位置から最も近い、壁か床か確定していないマスへ向かう
    • 幅優先で探索し、探索の一手目の遷移を覚えておいてそれを出力
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <tuple>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;

const char FORWARD      = 'F';
const char BACKWARD     = 'B';
const char ROTATE_LEFT  = 'L';
const char ROTATE_RIGHT = 'R';
typedef int direction_t;
const direction_t RIGHT = 0;
const direction_t UP    = 1;
const direction_t LEFT  = 2;
const direction_t DOWN  = 3;
direction_t rotate(direction_t dir, int deg) {
    return (dir + deg / 90) % 4;
}
pair<int,int> from_direction(direction_t dir) {
    switch (dir) {
        case RIGHT: return {  0,  1 };
        case UP:    return { -1,  0 };
        case LEFT:  return {  0, -1 };
        case DOWN:  return {  1,  0 };
    }
    assert (false);
}

const int inf = 20151224;
const int H = 37;
const int W = 37;

int main() {
    array<array<char,W>,H> field = {};
    array<array<int,W>,H> seen = {};
    auto nearest_unkown = [&](int cy, int cx) {
        array<array<bool,W>,H> used = {};
        queue<tuple<int,int,direction_t> > que;
        used[cy][cx] = true;
        que.emplace(cy, cx, -1);
        while (not que.empty()) {
            int y, x; direction_t fst; tie(y, x, fst) = que.front(); que.pop();
            repeat (d,4) {
                int dy, dx; tie(dy, dx) = from_direction(d);
                int ny = y + dy;
                int nx = x + dx;
                direction_t nfst = fst == -1 ? d : fst;
                switch (field[ny][nx]) {
                    case '\0':
                        return nfst;
                    case '#':
                        break;
                    case '.':
                        if (not used[ny][nx]) {
                            used[ny][nx] = true;
                            que.emplace(ny, nx, nfst);
                        }
                        break;
                }
            }
        }
        assert (false);
    };

    int y = H/2, x = W/2;
    direction_t dir = RIGHT;
    auto think = [&](int input) {
        if (input == inf) return FORWARD;
        if (seen[y][x] != 0xf) return ROTATE_LEFT;
        direction_t fst = nearest_unkown(y, x);
        return
            fst == rotate(dir,   0) ? FORWARD :
            fst == rotate(dir,  90) ? ROTATE_LEFT :
            fst == rotate(dir, 270) ? ROTATE_RIGHT :
                                    BACKWARD;
    };

    char last_cmd = '\0';;
    int last_input;
    int input = -1;
    while (true) {
        // input
        last_input = input;
        cin >> input;
        if (not cin) break;
        // update
        if (last_cmd == FORWARD  and         last_input >= 1) { int dy, dx; tie(dy, dx) = from_direction(dir); y += dy; x += dx; }
        if (last_cmd == BACKWARD and input == last_input + 1) { int dy, dx; tie(dy, dx) = from_direction(dir); y -= dy; x -= dx; }
        if (last_cmd == ROTATE_LEFT)  dir = rotate(dir,  90);
        if (last_cmd == ROTATE_RIGHT) dir = rotate(dir, 270);
        int dy, dx; tie(dy, dx) = from_direction(dir);
        repeat (i,input+2) {
            int ny = y + i * dy;
            int nx = x + i * dx;
            if (ny < 0 or H <= ny or nx < 0 or W < nx) break;
            if (i == input+1) {
                field[ny][nx] = '#';
            } else {
                field[ny][nx] = '.';
                seen[ny][nx] |= 1 << dir;
            }
        }
        char cmd = think(input);
        // output
        cout << cmd << endl;
        cout.flush();
        last_cmd = cmd;
    }
    return 0;
}