以下のレースゲームのシミュレーションを行うプログラムを作成せよ。
また、そのプログラムに関して、実装した範囲および仕様以外の拡張（ドライバの追加やルールの拡張）を行った箇所について、説明をReport.txtに記せ。特に拡張を行った場合、必ず入力方法を記述せよ。仕様を過不足無く実装した場合はそのように記述すること。
「過不足ない」とは「指定されたものは全てある」かつ「指定されたもの以外には何もない」の意味であることに注意せよ。
2/8(木) 23:59（日本時間/T2SCHOLA時間）
矩形の領域に東西、南北に延びる道路があり、ここを走る車両の移動をシミュレーションする。 各車両は1つ以上の目的地を持ち、最後の目的地にある駐車場に止める。 全ての車両が駐車場に入ったらシミュレーションの終了である。
- 道路は東西と南北に延びている。（対象の矩形領域内では）途中で切れたりすることはないものとする。
- 対象の矩形領域は、東西を「南北に延びる二本の道路の間」、南北を「東西に延びる二本の道路の間」で定義する。そのため、矩形の外縁部には必ず道路が存在する。
- 矩形領域の西にある南北の道路は、x座標が0であるとする。そこから東に向かってx座標が増加する。最も東の道路のx座標を
Rとする。（R > 0） - 矩形領域の南にある東西の道路は、y座標が0であるとする。そこから北に向かってy座標が増加する。最も北の道路のy座標を
Tとする。（T > 0） - 本シミュレーションでは全ての座標を整数で表せるものとする。各道路はx座標あるいはy座標が整数の位置を南北あるいは東西に延びている。
- x座標が0以上
R以下、y座標が0以上T以下であるような整数の座標で表せる箇所のうち、道路上にあるものを道路座標と呼ぶ。 - 道路が交差する道路座標を交差点と呼ぶ。
- 平行な道路は、必ず2以上離れている。
例えば、領域についてR = 10、T = 6とする（つまり東西に距離10、南北に距離6の矩形）。
南北に延びる道路がx = 0、x = 3、x = 8、x = 10とし、東西に延びる道路がy = 0、y = 4、y = 6とする。
この場合、道路座標(3, 4)は交差点であり（x = 3とy = 4の交差）、道路座標(5, 4)は交差点ではない。
なお、上の説明からわかる通り、必ず領域にはx = 0、x = R、y = 0、y = Tの道路が含まれる。
- 矩形領域内には必ず1つ以上の車両が存在する。
- 車両は道路座標上に存在する。（矩形領域の外側に出ることは許されない）
- 車両には向きが存在する。存在する道路を通る向きでなければならない。（南北に通る交差点でない道路座標上で東西を向くことはない）
- 車両はUターンできない。
- 車両が向きを変えられるのは交差点のみである。
- 進行方向が同じ車両は各道路座標上に高々1つしか存在してはいけない。進行方向が異なればそれぞれに1つずつ存在して良い。（対面交通をイメージすると良い）
- 交差点上には東西南北それぞれに1台ずつ、最大4台存在できる。
- シミュレーションは離散的に「ステップ」という単位で行われる。
- 1ステップ毎に、各車両は高々1だけ東西または南北に移動する。言い換えると、車両は1ステップ経ると、同じ場所にいる（動かない）、北に1移動する、南に1移動する、東に1移動する、西に1移動する、のいずれかの状態に移る。
- 交差点は「同じ方向に進もうとしている車が二台以上にいる」場合、以下の優先順位にしたがって優先車を決定し、優先車だけが進行を許される。
- 直進で入る車があればその車が優先車である。
- 直進で入る車がないが、左折で入る車があればその車が優先車である。
- （したがって右折で入る車は常に優先されない）
- 交差点上で衝突することは考えない。（南北方向、東西方向それぞれで全て直進する車両がいても、安全に次のステップで移動しているものとする）
- 移動しようとしている方向の車が進んでいなかったり、交差点から入ろうとしている先の車が止まっている場合、交差点で優先車でない場合、その車は動かない。
- 前の車が進んでいるのであれば、1つ前のステップ
- 「一周ぐるっと回る」ように車両がつながっているとこの説明では動くか動かないか定まらない（動くといっても動かないと言っても説明上は整合する）。今回の課題ではこのようなケースが起こらないようにするので考えなくて良い。
- 車両は少なくとも1つの目的地を持つ。これらを全て回ると、最後の目的地に駐車する。
- 目的地への進み方はドライバによって決定される。
- 駐車するのは、最終目的地に到着した次のステップである。（特殊な移動とする）
- 駐車は特殊な"向き"で、複数の車両が同じ座標に存在して良いし、他の向きの車両とは干渉しない。
- 駐車した後は動かない。全ての車両が駐車するとシミュレーションが終了する。
ドライバは以下の2種類を設定する。 なお、共通して交差点以外の道路座標では前の車両にぶつからない限り直進する（向いている方向に進む）ものとし、目的地は与えられた順番に回るものとする。
- 今の向きで進行することで目的地との距離が縮むなら交差点を直進する。縮まない（進行方向の軸の座標が同一または離れる方向を向いている）ならば目的地の距離が縮む方向へ曲がる。真後ろが目的地の場合、左折する（これにより真後ろでなくなるので到着できる）。
- 今の向きの先に目的地があるならば直進する。そうでなければ左右のうち、目的地の距離が縮む方向へ曲がる。真後ろが目的の場合、左折する。
どちらのドライバも賢くはないが、気にしないこと。
- 全ての車両の初期位置と目的地は交差点ではない。また、外縁部でもない。（つまり
0 < x < Rかつ0 < y < T） - 車両の次の目的地は一つ前の目的地とは異なる道路座標である。また、車両の初期位置と最初の目的地は異なる道路座標である。
- 車両数
N：1 <= N < 10 - 東西の幅
R：3 < R <= 100 - 南北の幅
T：3 < G <= 100
以下のようになっている。
N R T
0 x1 x2 ... xi R
0 y1 y2 ... yj T
（以下N行の車両設定）
1行目に車両数N、東西の幅R、南北の幅Tが空白を開けて与えられる。
2行目には南北に走る道路のx座標が、3行目には東西に走る道路のy座標が昇順で与えられる。これらは0から始まりR（東西の道路はT）で終了する。隣り合う座標は差が1より大きい。
4行目以降のN行は車両設定であり、次の書式である。
ドライバの種類 初期x座標 初期y座標 初期の向き 目的地の数t 目的地1のx座標 目的地1のy座標 ... 目的地tのx座標 目的地tのy座標
それぞれの内容は以下の通り
- ドライバの種類は1か2。それぞれ上で説明した1か2を表す。
- 初期x座標、初期y座標は数字で与えられる。
- 向きは北向きを表す
N、南向きを表すS、東向きを表すE、西向きを表すWのどれかである。
出力は、以下のブロックの繰り返しである。
- 何ステップ目かを表す1行（
nステップ目をstep nと表示）、nは1から始まりブロック毎に1ずつ増加する - 各車両の状態を表す
N行
各車両の状態は以下のようになっている。
x座標 y座標 現在の向き 次のステップの向き
向きは入力同様の北向きを表すN、南向きを表すS、東向きを表すE、西向きを表すWに加え、最後の目的地に到着して駐車したことを表すGの5種類がある。
次のステップの向きは、交差点以外では現在の向きと同一であり、交差点や最終の目的地に到着した際に現在の向きと異なるものとなる。また、次のステップで移動できない（移動先が詰まっていて進まない）場合であっても曲がるつもりであればそちらの向きを出力する。（つまり実際に次のステップで出力される「現在の向き」と一致する必要は無い）
最終目的地に到着した場合は、「次のステップの向き」がGとなり、またそれ以降のステップでは現在の向き、次のステップの向きともにGとなる。
全ての車両の現在の向きがGになったステップを出力した後終了する。
上記の入出力は全てファイルに対して行う。
入力は実行時引数の第1引数として与え、出力はその後ろに.logというファイル名を付けたものとする。
例えば以下のコマンド
> java Main5 sample0-1.txt
を実行すると、sample0-1.txtというファイルから入力フォーマットに従って入力を読み込み、sample0-1.txt.logというファイルに出力フォーマットに従った出力を書き込む。
なお、引数を与えなかった場合や2つ以上与えた場合の挙動は自由にして良い。（例えば引数がない場合に特定のファイルを対象にする、2つで出力先を決定する、複数与えて順に実行する、などを自身の開発のしやすさに応じて決めて良い）
また、標準入出力やエラー出力の利用についても特に限定はしない。
入力例はsample0-x.txtからsample4-x.txtまで用意されている。（xは0から始まり、いくつか存在）
対応する出力例はsample0-x_output.txtからsample4-x_output.txtである。（Main5の出力するファイルに上書きされないように別のファイル名にしている）
比較はdiffコマンドなどを用いると良い。（Linux/Unix系列であればdiffコマンドは標準で入っているはずである。Windowsならばfcコマンドを用いると良い。）
それぞれの入力例の使っている機能は以下の通りである。
sample0-x.txt：車両が1つだけで、目的地も1つだけ、さらに初期位置から向いている方向にいくだけでゴールできる。ドライバは1のみ。sample1-x.txt：車両が1つだけで、目的地も1つだけだが、目的地には交差点で曲がる必要がある。ドライバは1のみ。sample2-x.txt：複数の車両があるが、目的地は1つだけ、いくつかの車両は交差点で曲がる必要がある。ドライバは1のみ。ただし同じ交差点に同時に入ることがないように調整されている。sample3-x.txt：車両が複数あり、それぞれ複数の目的地が設定される。ドライバは1か2。交差点に同時に入ることがないように調整されている。sample4-x.txt：車両が複数あり、複数の目的地が設定される。ドライバは1か2。いくつかの車両が交差点に同時に入ることがある。sample5.txt：車両が輪を作って動く。「車両の移動について」に述べた通りこれが解ける必要は無いが、判定ができた場合に利用すること。（「輪ができたら動けないようにする」という方針では、ステップ6で初めて輪ができるので、ステップ7が全員動けなくなるはずである。）
採点についても大まかにはこの分類に従って行う。（ただしsample5.txtは拡張として扱う）
ドライバの種類を追加する（最短経路を通るようにする、目的地の到着順序を変更する、速度変更をかのうにする、など）、道の一部をUターン可能にするなど、ある程度自由にして良い。 ただし、拡張する場合は既存の入出力に変化がないようにすること。特に仮定しているルールを変更する場合（本来Uターンは不可能である）に答えが変わるような拡張にならないように、入力のフォーマットが干渉しないよう気をつけること。
以下の制限事項に違反する場合、本課題の点数は自動で0点となるので注意すること。
Main5以外のクラスを最低でも3つ定義すること。ただしこの講義は設計の講義ではないため、クラスの設計内容に関しては評価の対象としない。Main5以外のクラスは無名パッケージ以外のパッケージ内に存在すること。（パッケージ名は指定しないので自由に設定せよ）- 複数の
staticではないフィールドやメソッドを実装すること。（staticフィールドやstaticメソッドを実装すること自体は問題ないが、実装の大半がそれらの参照・実行で占められている場合は0点とする） - 入力例に対して出力例を読み込むなど、明らかにシミュレーションをしていないような実装をしないこと。
なお、盗用・剽窃などの行為を行った場合には本課題だけでなく本講義の得点そのものを0点とする。
- 入力は正しく条件を満たす場合に動作すれば十分だが、正しくない入力（パラメータや番号が範囲、制限を無視など）に対して、プログラムを停止させるか、解釈を決めて続行するか、エラーメッセージを出力するかなどについては自由に決めてよい。
- このシミュレーションは容易にシミュレーションが終了しない状態を作り出すことができる。例えば目的地の回り方が矩形となるような車を、矩形の長さ以上の数で一列に並べて開始すれば、誰も交差点を進めなくなりスタックして（全ての車が移動不能で行き詰まって）しまう。現状は終了条件が全ての車のゴールなので、どれだけステップ数を進めても終了しない。今回のサンプルや採点で用いる例はこのようなスタックが起こらないものと仮定する。
- なお、簡単な解決策としては「1ステップで誰も動かなかったら終了」という判定を導入すれば良い（全車両がゴールすれば誰も動かないので、考え方はほとんど同じ）。ただし、例えば拡張で「ランダムに止まる」ドライバなどを想定すると誤判定を起こす可能性もある。