結果

問題 No.331 CodeRunnerでやれ
ユーザー mamekinmamekin
提出日時 2016-04-07 19:51:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 723 ms / 5,000 ms
コード長 2,742 bytes
コンパイル時間 1,816 ms
コンパイル使用メモリ 126,316 KB
実行使用メモリ 25,232 KB
平均クエリ数 1954.71
最終ジャッジ日時 2024-07-16 23:36:07
合計ジャッジ時間 10,873 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 148 ms
25,220 KB
testcase_01 AC 175 ms
24,848 KB
testcase_02 AC 207 ms
24,592 KB
testcase_03 AC 414 ms
24,592 KB
testcase_04 AC 243 ms
25,220 KB
testcase_05 AC 231 ms
24,836 KB
testcase_06 AC 437 ms
24,848 KB
testcase_07 AC 547 ms
25,220 KB
testcase_08 AC 455 ms
25,232 KB
testcase_09 AC 314 ms
25,220 KB
testcase_10 AC 574 ms
24,580 KB
testcase_11 AC 412 ms
25,232 KB
testcase_12 AC 524 ms
25,220 KB
testcase_13 AC 590 ms
24,836 KB
testcase_14 AC 415 ms
24,592 KB
testcase_15 AC 459 ms
24,836 KB
testcase_16 AC 723 ms
24,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

void minDist(const vector<string>& plane, char empty, int y0, int x0, vector<vector<int> >& dist)
{
    int dy[] = {0, 0, -1, 1};
    int dx[] = {-1, 1, 0, 0};

    int h = plane.size();
    int w = plane[0].size();
    dist.assign(h, vector<int>(w, -1));

    queue<pair<int, int> > q;
    q.push(make_pair(y0, x0));
    dist[y0][x0] = 0;
    int n = 1;
    while(!q.empty()){
        queue<pair<int, int> > q1;
        while(!q.empty()){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            for(int i=0; i<4; ++i){
                int y1 = y + dy[i];
                int x1 = x + dx[i];
                if(0 <= y1 && y1 < h && 0 <= x1 && x1 < w && plane[y1][x1] == empty && dist[y1][x1] == -1){
                    q1.push(make_pair(y1, x1));
                    dist[y1][x1] = n;
                }
            }
        }
        ++ n;
        q = q1;
    }
}

const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};

int main()
{
    int y = 25;
    int x = 25;
    int d = 0;
    vector<string> grid(50, string(50, '?'));
    grid[y][x] = '.';
    queue<pair<int, int> > q;
    vector<vector<int> > dist;

    for(;;){
        int a;
        if(!(cin >> a))
            return 0;

        int y2 = y + dy[d];
        int x2 = x + dx[d];
        if(grid[y2][x2] == '?'){
            if(a == 0){
                grid[y2][x2] = '#';
            }
            else{
                grid[y2][x2] = '.';
                q.push(make_pair(y2, x2));
            }
        }

        bool isTurn = false;
        for(int i=0; i<4; ++i){
            int y3 = y + dy[i];
            int x3 = x + dx[i];
            if(grid[y3][x3] == '?')
                isTurn = true;
        }
        if(isTurn){
            cout << 'R' << endl;
            d = (d + 1) % 4;
            continue;
        }

        if(q.front() == make_pair(y, x))
            q.pop();
        int ty = q.front().first;
        int tx = q.front().second;
        if(dist.empty() || dist[ty][tx] != 0)
            minDist(grid, '.', ty, tx, dist);

        if(dist[y2][x2] != -1 && dist[y2][x2] < dist[y][x]){
            cout << 'F' << endl;
            y = y2;
            x = x2;
        }
        else{
            cout << 'R' << endl;
            d = (d + 1) % 4;
        }
    }
}
0