PKU1739-Tony's Tour

題目：http://poj.org/problem?id=1739
給一張大小N*M的地圖(最多8*8)，上面有一些道路【.】和障礙物【#】
Tony想從農場(最左下角格)走到市場(最右下角格)，並且經過所有可以走的格子
試問有幾種不一樣的走法？

類似的問題是USACO Training544 Betsy's Tour，附上翻譯網連結參考：
http://www.nocow.cn/index.php/Translate:USACO/betsy

程式碼：http://codepad.org/WEfG5OPf
這裡說個小插曲，傳到PKU上吃了好幾次CE、原來是常數的問題
果然const安定。(見第9和第11行)

教學文章：http://blog.imnettle.net/index.php/archives/168
這是一道經典的插頭DP(以路徑為主體的狀態壓縮DP)
事實上一般提供的方法都是求「走過全部可走格並回到原點」的路徑數
這種給定起點終點的問題，其實只要稍加修改地圖就能達成

好比說範例測資2就變成這樣：

#..
...

.#.

...

尾巴加上兩條row，最後一條空著、倒數第二條只留下頭尾空格

如此的迴路就和這道問題的路徑等價

雖然看起來很可怕

不過實際在紙上畫一遍以後(選有正方形格子的紙張)

就能理解其中精妙之處了