結果

問題 No.331 CodeRunnerでやれ
ユーザー kimiyuki
提出日時 2016-06-10 03:13:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,554 bytes
コンパイル時間 982 ms
コンパイル使用メモリ 96,936 KB
実行使用メモリ 95,136 KB
平均クエリ数 0.76
最終ジャッジ日時 2024-07-16 23:56:46
合計ジャッジ時間 8,501 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 1 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cstdio>
#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 DOWN = 2;
const direction_t LEFT = 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 = {};
int y = H/2, x = W/2;
direction_t d = RIGHT;
auto nearest_unkown = [&]() {
array<array<bool,W>,H> used = {};
queue<tuple<int,int,direction_t> > que;
used[y][x] = true;
que.emplace(y, x, -1);
while (not que.empty()) {
int y, x; direction_t fst; tie(y, x, fst) = que.front();
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);
};
auto think = [&](int input) {
if (input == inf) return FORWARD;
if (seen[y][x] != 0xf) return ROTATE_LEFT;
direction_t fst = nearest_unkown();
return
fst == rotate(d, 0) ? FORWARD :
fst == rotate(d, 90) ? ROTATE_LEFT :
fst == rotate(d, 270) ? ROTATE_RIGHT :
BACKWARD;
};
char last_cmd = '\0';;
int last_input;
int input = -1;
while (true) {
last_input = input;
cin >> input;
if (not cin) break;
if (last_cmd == FORWARD and last_input >= 1) { int dy, dx; tie(dy, dx) = from_direction(d); y += dy; x += dx; }
if (last_cmd == BACKWARD and input == last_input + 1) { int dy, dx; tie(dy, dx) = from_direction(d); y -= dy; x -= dx; }
if (last_cmd == ROTATE_LEFT) d = rotate(d, 90);
if (last_cmd == ROTATE_RIGHT) d = rotate(d, 270);
int dy, dx; tie(dy, dx) = from_direction(d);
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[y][x] = '#';
} else {
field[y][x] = '.';
seen[y][x] |= 1 << d;
}
}
char cmd = think(input);
cout << cmd << endl;
cout.flush();
last_cmd = cmd;
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0