有一人棋子，其1,6面2,4面3,5面相對，現給出一個M*N的棋盤，棋子起初處于(1,1)點，
擺放狀態給定，現在要求用最少的步數從(1,1)點翻滾到(M，N）點,并且1面向上
演算法分析 比較容易想到的演算法是寬度優先搜索演算法。由于搜索樹的枝樹是3叉，十分容易“超時”，
即使加了剪枝條件效果仍舊不明顯。
我們對問題進行分析：對于一個棋子，其總共只有24種狀態。在(1,1)點時，其向右翻滾至(2,1)點，
向上翻滾至(1,2)點。而任意（I，J）點的狀態是由（I-1，J）和（I，J-1）點狀態推匯出來的。
那么，如果規定棋子只能向上和向右翻滾，則可以用動態規劃的方法將到達（M，N）點的所有可能的
狀態推匯出來。而如果只能向上和向右翻滾能夠到達(M,N)點的話，這種方法一定是最優的。
所以，我們從（1，1）開始進行寬度優先搜索，每擴展出一個節點變做一次動態規劃，
直到動態規劃找到解，或者寬度優先搜索找到解為止，這樣即可以保證最優解。
用簡單搜索容易超時，當M,N較大可以用動態規劃
對于一個棋子，總共只有24種狀態。在(1,1)點時,其向右翻滾至(2,1)點,向上翻滾到(1,2)點.
而任意(I,J)點的狀態是由(I-1,J)和(I,J-1)點狀態推匯出來，所以如果規定棋子只能向上和向右
翻滾，則可以用動態規劃的方法將到達(M,N)點的所有可能狀態推匯出來.顯然,從(1,1)到達(M,N)這些
狀態的路徑最優的。如果這些狀態中有1面向上的，則已求出解.如果沒有，則可以從(M,N)點開始廣度
搜索,以(M,N)點狀態組作為初始狀態,每擴展一步時,檢查當前所得的狀態組是否有狀態與到達格子的狀態組
中狀態相同，如果有，則由動態規劃的最優性和廣度搜索的最優性可以保證求出最優解.
uj5u.com熱心網友回復：
首先，這不叫棋子叫骰子。1面向上時，向X或Y方向滾4步又恢復成1面向上。
所以先把X、Y方向整4步走掉：S1 = (((M-1)\4) + ((N-1)\4)) * 4
余下的距離
M2=(M-1) Mod 4
N2=(N-1) Mod 4
等價于求 (1,1) 走到 (M2+1,N2+1) 的解。最多是5x5的格子，骰子6個面，5*5*6=120 種狀態。
無論用廣度還是深度都很容易把到達這個120種狀態的最少步數求出來。
只要求出一次，任何的(M,N)按照上面求得(M2,N2)，取 S2 = (M2,N2,面1)的最少步數
最終步數就是 S1+S2
uj5u.com熱心網友回復：
更正：取 S2 = (M2+1,N2+1,面1)的最少步數uj5u.com熱心網友回復：
對于任意的M、N，這會不會出現“無解”的情況？
uj5u.com熱心網友回復：
都有解。比如就在(1,1)上要翻出其余六一個面：
A：右、下、左、上，就把原先的左側面翻到上面。一共有4個起始方向，所以4個側面都可以翻到上面。
B：右、下、下、左、上、上，原先的底面翻到了上面。
uj5u.com熱心網友回復：
uj5u.com熱心網友回復：
如何寫代碼，誰會寫啊uj5u.com熱心網友回復：
演算法問題，給了思路代碼你自己寫啊。畢竟不是幾分鐘就能寫完的代碼，誰這么有空啊。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/92520.html
標籤：資源
上一篇：vb中winsock接受問題
下一篇：誠心請教(曲線圖)