結果

問題 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;
}
0