PKU1475-Pushing Boxes

題目：http://poj.org/problem?id=1475
給一個R*C(20*20)的棋盤
S是人的起點、B是箱子，想用最少推的次數把箱子推到T目標格
並且輸出整個推的操作序列，如果推的次數一樣則選總次數最少


程式碼：http://codepad.org/PMvxo8mN
網路上說它叫嵌套BFS
諸如「人移動是為了推箱子，以箱子為主進行BFS」這類的話就不多講了

檢討「我們要搜的狀態是什麼？」就能發現
箱子的座標和人的座標都是決定因素，共20*20*20*20個狀態
但事實上，箱子的座標/人在箱子的哪一側更為精簡
因為只要人在同側都能自由移動，確切在哪一格並不太重要
於是簡化成20*20*4個狀態

所以整個BFS_by_box的架構就是不斷重複：
1.讀入佇列的狀態now，檢查箱子是否已經在終點
2.試著利用now造出「把箱子往方向i推」的狀態goal
---判斷障礙物
---呼叫BFS_by_man，確認人能走到可推的位置/走法

注意一些小bug，好比說BFS_by_man的時候得把當前的箱子也當成障礙
參考一下discuss的建議，把搜索順序定義NSWE

有了細心、耐心、愛心、勇氣、毅力以後，此題得解