ほんの数時間前、ICFPC-2012コンテストが始まりました。これは
週末を通して続きます。 興味のある人が参加する時間があることを期待して、このコンテストのタスクを移すことにしました。
タスクは非常に理解しやすいので、行ってください。
タスクに変更が加えられました。
水 、
テレポーター 、
あごひげ 、
スーパーストーン 。
スコットランドで発見されたラムダス鉱山！ あなたの仕事は、地雷図を読むことでロボット用のプログラムを作成できるようにすることです。
美しいシミュレーターへのリンク：
icfp.stbuehler.de/icfp2012基本的なルール
- ロボットは未知の文字をスキップします（L、R、U、D、W、Aのみが認識されます）。
- ロボットがコマンドを実行できない場合、この移動は何も行いません。
- ロボットが移動すると、マップは以下で説明するルールに従って更新されます。
- マップを更新した後、完了の条件が確認されます。
カードの説明
マップはm×nセルのグリッドで、座標（1,1）は
下と左にあります。
各セルには、次の文字のいずれかが含まれます。
- R-ロボット
- * -石
- L-閉じた出口
- 。 -土地
- ＃ -壁
- \ -λ
- O-オープン出力
- 」 "-スペース、空のセル
何も壁を貫通することはできません。 m×nフィールドを超えるものはありません。 ロボットは地球を掘り、λを収集し、石を動かすことができます。 石が落ちています。 石はロボットを殺すことができます。
初期状態の例：
ロボットコマンド
ロボットの座標（x、y）：
- L-左側、（x-1、y）
- R-（x + 1、y）の右側
- U-上、（x、y + 1）
- D-ダウン、イン（x、y-1）
- W-待って、何もしない
- A-鉱山探査を中止する
出口が開いているケージ、空のケージ、地球のあるケージ、およびλのあるケージに移動できます。 石の後ろに空いている場所があれば、石でケージ内に移動できます（左右のみ）。 ケージを離れた後、ロボットは常にケージ内に空隙を残します。
マップの更新（シミュレーション）
ロボットの動きがシミュレーションステップを通過した後。 この段階では、古い状態は常に新しい状態に読み書きされます。 座標の次の順序：（1、1）、（2、1）、...、（n、1）、（1、2）...（n、m）。
ルールは上から下に順番にチェックされます。 1つが機能した場合、次は機能しません。
- 石の下に空洞があります-石は1セル下に落ちます。
- 石の下に石があり、右側が空で、右側が空です-石は右斜めに落ちます。
- 石の下に石があり、左が空で左下が空です-石は左斜めに落ちます。
- 石の下-λ、空は右、空は右下-石は右斜めに落ちます。
- 残りのセルは移動しません。
カードにλがもうない場合、すべての閉じた出力が開きます。
落下したばかりの石の下にロボットが立っていた場合、ロボットは故障します。これは敗北です。
1つのシミュレーションステップで、石は1セル下に落ちます。
異なる側からの石が1つのセルに落ちることがあります。 この場合、1個の石がこのセルにあります。
完了条件
- ロボットがオープンリフトに入る-WIN
- ロボットがコマンドA-WINを実行しました
- 砕石ロボット-失う
入力/出力
stdinからの入力、stdoutへの出力
一部の行が最大行長より短い場合、右側にスペースが埋め込まれていると見なされます。
最初は、各マップに開いている出口はありません。 正確に1つのロボットと1つの閉じた出力があります。
カードは1000×1000以上にすることができます。
得点
各ステップ-1
収集されたλ+25
コマンドA実行時の収集されたλ+25
出力+50に達した時点で収集されたλ
テストカードの受け渡しオプションをテストするためのスクリプト：
検証ツール制限
プログラムは、1 Gb RAMを搭載した32ビットDebian-linuxで実行する必要があります。
150秒後、プログラムはSIGINTを受信し、その後10秒間応答を出力します。
これらの10秒後にSIGKILLと0ポイント。
競技中、1〜4回のルール変更が行われます。
英語の詳細：
icfpcontest2012.wordpress.com最初のルール変更：水
いくつかの鉱山が洪水を始めました！
マップの説明の後に、空の行と3つのパラメーター（行ごとに1つ）があります。
水0
フラッディング0
防水10
（0、0、10）-デフォルト値。
水は、水位の初期値を示します（座標を1から数え、水位が0になる場合があることに注意してください）。
フラッディング-水の到着速度。 0の場合-水がまったく届かない。 N> 0の場合、Nステップの直後に水位が1増加します。
防水-ロボットの保護レベル、潜水なしで水中を何歩歩けるか。 それが現れるとすぐに、ステップカウンターがリセットされ、再び潜ることができます。
ロボットは、y座標
<=水位の場合、水中にあると見なされます。
ロボットが水中で防水ステップを超える時間を費やすと、ロボットは壊れます。
2番目のルール変更：テレポーター
テレポートがゲームに追加されました（ドックのダイビングボードと呼ばれます）。 テレポートの入力は文字A..Iで示され、テレポートの出力は数字1..9です。
テレポートに入ると、テレポートの入り口と出口が消えます。
どのエントリがどの出口につながるかは、フレーズのあるカードの後に記述されています。
トランポリンAターゲット1
トランポリンBターゲット1
トランポリンCターゲット2
3番目のルール変更：バイオマスとカミソリ
追加されたひげ-Wとカミソリ-
！ 。 マップの最後に、カミソリが持っているカミソリの数と、ヒゲが成長する速さが書かれています。
成長15
かみそり2
デフォルトでは、成長値（g）は25、カミソリの数は0です。
すべてのgステップで、stepsが空の場合（つまり、対角線を含む）、隣接する8つのセルを埋めます。
かみそりは、ひげに対処する唯一の方法です。 Sコマンドを実行した後、カミソリ（ロボットにある場合）が適用され、8つの隣接セルのひげをきれいにします。
最後のルール変更：高次の石
@-高次の石を追加し、その中にλが隠れています。 任意の高さから落下すると、石が壊れ、その場所にλが表示されます。
難易度評価について
タスクは複雑なボールダーダッシュに非常に似ていることに注意してください。一般的な場合、その通過はNP完全タスクです。
証明は非常に簡単です：解がグラフでハミルトニアンサイクルを見つけることに等しい迷路があり、これはよく知られている問題です：
wikiハミルトニアンサイクル