問題一覧 > 通常問題

No.331 CodeRunnerでやれ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 47
作問者 : uwiuwi
8 ProblemId : 877 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-12-23 23:19:26

問題文

あなたは迷路のどこかにいて、上下左右のいずれかを向いています。迷路について、以下のことがわかっています。

  • 迷路は長方形のグリッドであること
  • 迷路の外側は空きセルからなること
  • 迷路は壁または空きセルのみからなること
  • ゴールのセルは、迷路の周上にあり、隅でないどれか1個の空きセルであること
  • ゴール以外の迷路の周を構成するセルは壁であること
  • 壁のセルには入れないこと
  • 初期位置からゴールまで隣接する空きセルのみをたどって必ずたどりつけること
  • 初期位置はゴールではない空きセルであるということ
あなたがとれる行動は以下の通りです。
  • F : 現在位置から現在の向きに1セルだけ前進する。前進出来ない場合はその場にとどまる。
  • B : 現在位置から現在の向きから1セルだけ後退する。このとき向きは変化しない。後退出来ない場合はその場にとどまる。
  • L : 位置をかえないまま、向きを反時計回りに90度回転する。
  • R : 位置をかえないまま、向きを時計回りに90度回転する。
あなたが初期状態もしくは各行動後にわかる値は以下の通りです。
  • 現在位置から現在の向きに何セルまで進めるか
  • ゴールしたかどうか
初期位置から行動を繰り返してゴールまでたどり着いてください。

この問題はリアクティブです。
入力 → 出力 → 入力 → 出力 → ... → 入力("Merry Christmas!") → 終了
という流れになります。入力も出力も1ステップあたり1行で行います。

入力

入力行は、次のロジックで決定されます。末尾に改行が付きます。
  • もし現在位置がゴールであれば "Merry Christmas!".
  • それ以外の場合は、現在位置から現在の向きに進めるセル数。無限に進める場合は$20151224$.
たとえば次の5*4の迷路において、壁を"#", 空きセルを".", 現在位置を"v"で表し、下を向いているとする場合、進めるセル数は2となります。
####
#.v#
#..#
#...
####

迷路と初期位置については、問題文冒頭の制約をすべて満たすことが保証されています。
なお、迷路のサイズは与えられませんが、縦のサイズをN, 横のサイズをMとした場合、
$3\le N\le 20,$
$3\le M\le 20$
を満たします。

出力

出力は以下のいずれかでなければなりません。出力したあと必ず改行してflushしてください。 また"Merry Christmas!"が入力として与えられた場合、ゴールに到着したため、終了してください。

  • F
  • B
  • L
  • R
これらは以下の行動に対応します。
  • F : 現在位置から現在の向きに1セルだけ前進する。前進出来ない場合はその場にとどまる。
  • B : 現在位置から現在の向きから1セルだけ後退する。このとき向きは変化しない。後退出来ない場合はその場にとどまる。
  • L : 位置をかえないまま、向きを反時計回りに90度回転する。
  • R : 位置をかえないまま、向きを時計回りに90度回転する。

サンプル

上記の迷路についてゴールするまでの流れを例示します。
入力 出力 状態
2
####
#.v#
#..#
#...
####
F
1
####
#..#
#.v#
#...
####
F
0
####
#..#
#..#
#.v.
####
L
20151224
####
#..#
#..#
#.>.
####
B
20151224
####
#..#
#..#
#>..
####
F
20151224
####
#..#
#..#
#.>.
####
F
Merry Christmas!
####
#..#
#..#
#..>
####

Note

writerの単純なプログラム(Java,Scanner)では10000stepsぐらいでTLEするようです。C++なら30000,40000steps程度はいけそうです。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。