結果

問題 No.331 CodeRunnerでやれ
ユーザー rickythetarickytheta
提出日時 2015-12-24 07:13:46
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 427 ms / 5,000 ms
コード長 2,987 bytes
コンパイル時間 1,714 ms
コンパイル使用メモリ 173,984 KB
実行使用メモリ 25,476 KB
平均クエリ数 498.94
最終ジャッジ日時 2024-07-16 22:41:18
合計ジャッジ時間 8,881 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 174 ms
24,976 KB
testcase_01 AC 154 ms
24,836 KB
testcase_02 AC 207 ms
25,220 KB
testcase_03 AC 381 ms
24,848 KB
testcase_04 AC 228 ms
25,220 KB
testcase_05 AC 233 ms
25,476 KB
testcase_06 AC 346 ms
24,848 KB
testcase_07 AC 342 ms
25,220 KB
testcase_08 AC 273 ms
24,976 KB
testcase_09 AC 348 ms
25,220 KB
testcase_10 AC 341 ms
24,836 KB
testcase_11 AC 270 ms
24,848 KB
testcase_12 AC 301 ms
25,220 KB
testcase_13 AC 343 ms
24,964 KB
testcase_14 AC 388 ms
25,232 KB
testcase_15 AC 270 ms
25,220 KB
testcase_16 AC 427 ms
24,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

int G[100][100];
int visited[100][100];
int main(){
  int px = 50, py = 50;
  int dir = 0;
  int dx[4] = {1,0,-1,0};
  int dy[4] = {0,1,0,-1};
  REP(i,100)REP(j,100)G[i][j]=-1;
  // -1 : unknown
  //  0 : none
  //  1 : wall

  // 訪れていない場所があったらそっちへ行く方針
  // 場所を訪れて、訪れたことが無かったら1周してデータを集める
  while(true){
    string s;
    cin>>s;
    if(s=="Merry")break;
    if(s=="20151224"){
      cout << "F" << endl;
      continue;
    }
    G[px][py] = 0;
    if(visited[px][py]==0){
      REP(i,4){
        cout << "R" << endl;
        dir=(dir+1)%4;
        cin>>s;
        if(s=="20151224")break;
        int cnt = atoi(s.c_str());
        REP(i,cnt){
          G[px+(i+1)*dx[dir]][py+(i+1)*dy[dir]] = 0;
        }
        G[px+(cnt+1)*dx[dir]][py+(cnt+1)*dy[dir]] = 1;
      }
      if(s=="20151224"){
        cout << "F" << endl;
        continue;
      }
      visited[px][py] = 1;
    }
    // bfs
    bool v[100][100];REP(i,100)REP(j,100)v[i][j]=false;
    v[px][py]=true;
    queue< pair< pii,vector<pii> > > Q;
    Q.push(make_pair(make_pair(px,py),vector<pii>()));
    int tx=-1,ty=-1;
    vector<pii> tpath;
    while(!Q.empty()){
      pair< pii,vector<pii> > P = Q.front(); Q.pop();
      int nx = P.first.first, ny = P.first.second;
      vector<pii> path = P.second;
      path.push_back(make_pair(nx,ny));
      REP(i,4){
        int nnx = nx+dx[i], nny = ny+dy[i];
        if(v[nnx][nny])continue;
        if(G[nnx][nny]!=0)continue;
        if(visited[nnx][nny]==0){
          tx = nnx;
          ty = nny;
          tpath = path;
          break;
        }
        v[nnx][nny] = true;
        Q.push(make_pair(make_pair(nnx,nny),path));
      }
      if(tx!=-1 && ty!=-1)break;
    }
    // trace path and go to (tx,ty)
    tpath.push_back(make_pair(tx,ty));
    REPR(i,tpath.size()){
      int vx = tpath[i].first - tpath[i-1].first;
      int vy = tpath[i].second - tpath[i-1].second;
      int ndir;
      if(vx==1)ndir = 0;
      if(vx==-1)ndir = 2;
      if(vy==1)ndir = 1;
      if(vy==-1)ndir = 3;
      if(dir%2 != ndir%2){
        cout << "R" << endl;
        cin >> s;
        dir = (dir+1)%4;
      }
      if(dir==ndir){
        cout << "F" << endl;
      }else{
        cout << "B" << endl;
      }
      if(!(tpath[i].first == tx && tpath[i].second == ty)){
        cin >> s;
      }
    }
    px = tx;
    py = ty;
  }
  return 0;
}
0