砂漠の旅行の問題

砂漠の旅行の問題
現在地点 S にいる旅人が、幅 N の砂漠を渡って、地点 G に行きたい
S 1 2 3 ... N G
1 升移動する場合は、食料を 1 単位消費する
砂漠の途中で保持する食料が 0 になったら移動ができなくなる
G に達した時点で、食料が 0 になっていてもよい
旅人が持つ事ができる食料は最大で 3 つ迄である
S には、食料が無限にあり、いくつでも補給できる
最初の状態では、砂漠には、食料はない
旅人は、食料を持っていれば、砂漠に食料を置く事ができる
砂漠に置く事ができる食料の個数は最大 2 個である
旅人は、砂漠に食料があり、保持数が 3 以内なら食料を拾う事ができる