Yukicoder No.331 CodeRunnerでやれ
これすき
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;
}