結果

問題 No.331 CodeRunnerでやれ
ユーザー tnakao0123
提出日時 2016-04-18 16:04:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 267 ms / 5,000 ms
コード長 4,140 bytes
コンパイル時間 731 ms
コンパイル使用メモリ 94,700 KB
実行使用メモリ 25,232 KB
平均クエリ数 284.94
最終ジャッジ日時 2024-07-16 23:38:56
合計ジャッジ時間 5,998 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 331.cc: No.331 CodeRunnerでやれ - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int H = 25;
const int W = 25;
const int HH = H * 2 + 1;
const int WW = W * 2 + 1;
const int INF = 1 << 30;

const int dxs[] = {1, 0, -1, 0}, dys[] = {0, -1, 0, 1};

/* typedef */

typedef pair<int,int> pii;

/* global variables */

int flds[HH][WW], dists[HH][WW];
bool used[HH][WW];
pii prvs[HH][WW];

/* subroutines */

void print_flds(int sx, int sy, int di) {
  for (int y = 0; y < HH; y++) {
    bool ok = false;
    for (int x = 0; ! ok && x < WW; x++)
      if (flds[y][x] >= 0) ok = true;
    if (! ok) continue;
    for (int x = 0; x < WW; x++) {
      if (sy == y && sx == x)
	switch (di) {
	case 0: cerr << '>'; break;
	case 1: cerr << '^'; break;
	case 2: cerr << '<'; break;
	case 3: cerr << 'v'; break;
	}
      else
	switch (flds[y][x]) {
	case -1: cerr << '?'; break;
	case 0: cerr << '.'; break;
	case 1: cerr << '#'; break;
	}
    }
    cerr << endl;
  }
  cerr << "-------------" << endl;
}

bool checked(int x, int y, int di) {
  while (x >= 0 && x < WW && y >= 0 && y < HH) {
    if (flds[y][x] != 0) return (flds[y][x] > 0);
    x += dxs[di], y += dys[di];
  }
  return true;
}

pii bfs(int sx, int sy) {
  //fprintf(stderr, "bfs(%d,%d)...\n", sx, sy);

  for (int y = 0; y < HH; y++)
    for (int x = 0; x < WW; x++) dists[y][x] = INF;
  dists[sy][sx] = 0;
  prvs[sy][sx] = pii(-1, -1);

  queue<pii> q;
  q.push(pii(sx, sy));

  int gx = -1, gy = -1;
  
  while (! q.empty()) {
    pii u = q.front(); q.pop();
    int &ux = u.first, &uy = u.second;
    //fprintf(stderr, "  (%d,%d)=%d\n", ux, uy, dists[uy][ux]);

    if (! used[uy][ux]) {
      gx = ux, gy = uy;
      break;
    }
    int vd = dists[uy][ux] + 1;

    for (int di = 0; di < 4; di++) {
      int vx = ux + dxs[di], vy = uy + dys[di];
      if (vx >= 0 && vx < WW && vy >= 0 && vy < HH &&
	  flds[vy][vx] == 0 && dists[vy][vx] > vd) {
	dists[vy][vx] = vd;
	q.push(pii(vx, vy));
	prvs[vy][vx] = pii(ux, uy);
      }
    }
  }
  if (gx < 0) {
    //fprintf(stderr, "no pos\n");
    return pii(-1, -1);
  }
  
  pii st(sx, sy), cp(gx, gy);
  for (;;) {
    pii pcp = prvs[cp.second][cp.first];
    //fprintf(stderr, "  %d,%d -> %d,%d\n",
    //cp.first, cp.second, pcp.first, pcp.second);
    if (pcp == st) break;
    cp = pcp;
  }

  return pii(cp.first, cp.second);
}

/* main */

int main() {
  memset(flds, -1, sizeof(flds));

  int x = W, y = H, di = 0, rot = 0;
  flds[y][x] = 0;
  used[y][x] = true;

  for (;;) {
    string s;
    getline(cin, s);
    if (s == "Merry Christmas!") return 0;

    int len = atoi(s.c_str());
    if (len >= 20151224) break;

    for (int i = 1; i <= len; i++)
      flds[y + dys[di] * i][x + dxs[di] * i] = 0;
    flds[y + dys[di] * (len + 1)][x + dxs[di] * (len + 1)] = 1;
    //print_flds(x, y, di);
    
    int di0 = (di + 1) & 3;
    for (; di0 != di; di0 = (di0 + 1) & 3)
      if (! checked(x, y, di0)) break;
    if (di0 != di) {
      char op;
      if (di0 == ((di + 3) & 3)) op = 'R', di = (di + 3) & 3;
      else  op = 'L', di = (di + 1) & 3;
      cout << op << endl; cout.flush();
      continue;
    }
    //fprintf(stderr, "di=%d,di0=%d\n", di, di0);

    pii v = bfs(x, y);
    int &vx = v.first, &vy = v.second;
    int vdi = (vx > x) ? 0 : (vy < y) ? 1 : (vx < x) ? 2 : 3;
    int dd = (vdi + 4 - di) & 3;
    //fprintf(stderr, "bfs(%d,%d)=%d,%d: %d->%d\n", x, y, vx, vy, di, vdi);

    char op;
    if (dd == 0)
      op = 'F', x += dxs[di], y += dys[di], used[y][x] = true;
    else if (dd == 3)
      op = 'R', di = (di + 3) & 3;
    else
      op = 'L', di = (di + 1) & 3;
    cout << op << endl; cout.flush();
  }

  for (;;) {
    puts("F"); cout.flush();

    string s;
    getline(cin, s);
    if (s == "Merry Christmas!") break;
  }
  return 0;
}
0