Description:
10x10のフィールドが有り、行0がスタート、行9がゴール。
列1-4では、車が一定速度で左に動いている。
列5-9では、車が一定速度で右に動いている。
左から出た車は右に入ってきて、逆も又然り。
同じ列に車が複数存在する事は有るが、その場合、車の速度は等しい。
ある列から蛙がスタートして、蛙が1歩下に動くorその場に留まる、車が動く、というのを繰り返し、
蛙がゴールの列まで辿り着く事が可能かどうかを答えよ。
Answer:
車だけを考えた時、盤面の状態は10パターンしかない。
よって、蛙の位置と状態パターンをペアを状態にして、同じ状態を避けるメモ付き探索。
Source: