結果

問題 No.331 CodeRunnerでやれ
ユーザー mamekin
提出日時 2016-04-07 18:53:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,720 bytes
コンパイル時間 1,586 ms
コンパイル使用メモリ 125,492 KB
実行使用メモリ 88,300 KB
最終ジャッジ日時 2024-07-16 23:35:55
合計ジャッジ時間 14,643 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

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] < dist[y][x]){
            cout << 'F' << endl;
            y = y2;
            x = x2;
        }
        else{
            cout << 'R' << endl;
            d = (d + 1) % 4;
        }
    }
}
0