結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0