ぱたへね!

はてなダイアリーはrustの色分けができないのでこっちに来た

PAIP 4.13 The Maze Searching Domain

GPSを使って迷路を解く問題。
昔よく似た問題を解いたような気がしますが、今回の迷路はこちらです。スタートが1で、ゴールが25です。

迷路はlistで表現しています。

maze_data = [(1,2),(2,3),(3,4),(4,9),(9,14),(9,8),(8,7),(7,12),(12,13),(12,11),
(11,6),(11,16),(16,17),(17,22),(21,22),(22,23),(23,18),(23,24),(24,19),(19,20),
(20,15),(15,10),(10,5),(20,25)]

実行結果はこうなります。1から25まで移動しています。

Consider:move from 20 to 25
Consider:move from 19 to 20
Consider:move from 24 to 19
Consider:move from 23 to 24
Consider:move from 22 to 23
Consider:move from 17 to 22
Consider:move from 16 to 17
Consider:move from 11 to 16
Consider:move from 12 to 11
Consider:move from 7 to 12
Consider:move from 8 to 7
Consider:move from 9 to 8
Consider:move from 4 to 9
Consider:move from 3 to 4
Consider:move from 2 to 3
Consider:move from 1 to 2
Action move from 1 to 2
Action move from 2 to 3
Action move from 3 to 4
Action move from 4 to 9
Action move from 9 to 8
Action move from 8 to 7
Action move from 7 to 12
Action move from 12 to 11
Action move from 11 to 16
Action move from 16 to 17
Action move from 17 to 22
Action move from 22 to 23
Action move from 23 to 24
Action move from 24 to 19
Action move from 19 to 20
Action move from 20 to 25

PAIPに表示形式を合わせてみました。 find_path(1,25)でこの結果を返します。

(1 2 3 4 9 8 7 12 11 16 17 22 23 24 19 20 25 )

ソースはGitHubにあります。
https://github.com/natsutan/PAIP/blob/master/ch4/gps2.py
https://github.com/natsutan/PAIP/blob/master/ch4/maze.py