結果
問題 | No.331 CodeRunnerでやれ |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
/* -*- 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;}elseswitch (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;elseop = '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;}