【東京大学】【優】幅優先探索
問題3
問題3は、プログラムを使って解いた。
まず、状況を定義する。
状況を簡単にするために、二つのセルにまたがるロボットのセルとセルの中間点をロボットの位置として考えることにする。こうすることで、ロボットの位置を一つの変数で表すことができる。
また、データを扱い易くする為にロボットの位置のとり方を工夫する。ロボットのセルとセルの中間に位置を取るので、マス目ではなく線の上に位置をとることになる。
Y
X
2
1
0
0 1 2 3 4 5 6 7 8
上の図のように座標を取る。ここで、Xの左の縦の線を(0,0)、Xの上の横の線を(1,0)、Xの右の縦の線を(2,0)、Yの左の縦の線を(0,1)とする。
### # # # #
####S #######
##### ######
## ######## # # # #
# G###### ###
# ### ###
# #
# # # #
#### # ###### #
## ##### # ######### # # # ##
与えられた表を上記の条件で書き直...