※ 引述《linkone (小豆豆)》之銘言：
: 題目網址:http://www.tcgs.tc.edu.tw/~sagit/luckycat/q10067.htm
: 這種有無限多種排列組合的題目真的是我想到死都想不出來
: 想了好幾種方式去掃但是好像都會有Bug
: 目前想到的方法是:
: 2
: 8 0 5 6
: 6 5 0 8
: 5
: 8 0 5 7
: 8 0 4 7
: 5 5 0 8
: 7 5 0 8
: 6 4 0 8
: 掃出禁止數目裡 個位數 十位數 百位數 千位數 裡沒有的數字 然後找出最短可以到達的
: 例如 個位數禁止數字裡 沒有 1 2 3 4 5 6 9
: 6往上調7就不行 所以往下調到五 只要調到五 其他的就可以直接調上去
: 但是我這樣一次只有考慮一個位數 不曉得這樣會不會有bug..
: 還是這是有牽扯到資料路徑問題.....
資料結構方面是一維的陣列int ary[10000]; // 0 ~ 9999
用來記錄到達此數字要轉幾步。
0 0 0 0 當成0
1 2 3 4 當成1234
初始化ary所有是-1，代表輪盤還未被轉到，或並未具意義。
那麼起始輪盤ary[8056] = 0;
目標輪盤ary[6508] = -3;
禁止輪盤ary[8057] = -2; ary[8047] = -2; ... 等等非常多。
轉輪盤的程序：
int d[2] = {1, -1}; // 轉右或轉左
for(int 位數 = 0; 位數 != 4; ++位數) // 0 ~ 3
for(int j = 0; j != 2; ++j)
轉輪盤函數(目前輪盤, 位數, d[j], 下一個輪盤);
將下一個輪盤轉換成數字：假設是8057好了。
如果ary[8057] == -3，達到目標。
ary[8057] == -1，ary[8057] = 轉輪盤的步數。
ary[8057] == -2，禁止，BFS不必處理。
ary[8057] == 某個正數(代表前次轉到的步數)，BFS不必處理。
BFS的實作方式希望您能上網查資料或查書。
提示可以用queue來實作，不必處理就代表不必再放到queue裡。
: 還有另外一題 給你 ax+by=d d為a跟b的最大公約數 找出|x|+|y|的最小值
: .... 上網看是歐基里德擴展演算法 .... 看都看不懂~ . ~
: 不曉得有沒有解釋較清楚的網站.. 麻煩各位嚕
這個wiki或google都有現成的程式碼...................
Bleed
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.115.229