IQCar的實作II——解題思路

　　上文簡單介紹了IQCar遊戲。接下來将描述用計算機如何求出它的解法。

　　學過資料結構的，第一感覺就是用“深度優先搜尋”或者是“廣度優先算法”。就是不停的嘗試每一種可能，直到到達解。然後将嘗試的過程輸出即可。

　　仔細觀察上文的圖檔，發現，每一輛車的可能性位置可能性非常少（由于車子隻能前後移動，故長度為3的車子隻有4種可能，長度為2的車子有五種可能）。那麼，則這些車子排列的可能性就不會多（原因是，如果車子多，則彼此之間的限制會很多，因為兩輛車不能擠在一個格子裡，如果車子少，雖然限制少但是車子少，必然總數少）。這樣，一般的題目，把所有的車子排列構成一個集合的話，這個集合中的元素不會很多（實際情況是，一般的題目，這個集合的元素在1200左右）。

　　想到這，我想到用圖論的方法求解。

　　所有的車子的一個位置排列，成為圖中的一個點，兩點之間的連線表示能從一個排列移動一個位置到另一個排列。題目中的初始狀态為圖中的一個點，達到解題條件的為另一個點（這樣的點可能不止一個），問題就轉化為在圖中從一個點找到到另一個點的通路。

　　這個求通路的有一個非常有名的算法，Dijkstra算法（最短路徑算法）。

　　那麼本問題就轉化為兩個步驟

　　1、根據輸入的初始狀态，生成一個集合，所有車子的一個位置排列為集合中的一個元素。并且為每一個元素建立他們之間的關系（有連線則表示能從一個排列移動一個位置到另一個排列，反之則無連線）。

　　2、用Dijkstra算法求出一條通路，這條通路也是最短通路，也就是最優解

　　注：寫完程式後，細細想來，在本題中，由于各連線的長預設都是1，Dijkstra算法其實就是廣度優先算法。

　　後文将具體的描述各個子產品的實作。