結果

問題 No.331 CodeRunnerでやれ
ユーザー kimiyukikimiyuki
提出日時 2016-06-10 03:25:02
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 296 ms / 5,000 ms
コード長 3,595 bytes
コンパイル時間 2,182 ms
コンパイル使用メモリ 97,584 KB
実行使用メモリ 25,460 KB
平均クエリ数 339.06
最終ジャッジ日時 2024-11-13 22:30:42
合計ジャッジ時間 7,478 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 148 ms
24,976 KB
testcase_01 AC 149 ms
24,580 KB
testcase_02 AC 195 ms
25,232 KB
testcase_03 AC 174 ms
24,848 KB
testcase_04 AC 210 ms
24,964 KB
testcase_05 AC 193 ms
24,836 KB
testcase_06 AC 199 ms
24,848 KB
testcase_07 AC 279 ms
25,460 KB
testcase_08 AC 243 ms
24,592 KB
testcase_09 AC 296 ms
24,580 KB
testcase_10 AC 187 ms
24,580 KB
testcase_11 AC 242 ms
24,836 KB
testcase_12 AC 267 ms
24,836 KB
testcase_13 AC 284 ms
24,836 KB
testcase_14 AC 295 ms
24,848 KB
testcase_15 AC 247 ms
24,836 KB
testcase_16 AC 274 ms
24,580 KB
権限があれば一括ダウンロードができます

ソースコード

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 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 = {};
    int y = H/2, x = W/2;
    direction_t dir = 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(); 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);
    };
    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(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) {
        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(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);
        cout << cmd << endl;
        cout.flush();
        last_cmd = cmd;
    }
    return 0;
}
0