07-搜索之bfs-資料下載頁(yè)
2025-07-24 02:45本頁(yè)面
【正文】 17 5 + 21 15 2022/8/21 43 ?最壞情況 N=10000，二叉樹有 10000層，結(jié)點(diǎn)總數(shù) 2100001。不可能枚舉所有表達(dá)式 本題的目標(biāo)：判斷葉子結(jié)點(diǎn)上是否有值能被 k 整除 =判斷是否有值，除以 k的余數(shù)為零。 計(jì)算中間值取余，不影響結(jié)果。 (a + b) % k = ( a % k + b % k) % k ? 因此只需記錄對(duì) k的余數(shù)。 2=k=100，每層結(jié)點(diǎn)最多 100個(gè)，不是指數(shù)級(jí)增加。 2022/8/21 44 4 7 17 5 21 15 每層最多 7個(gè)結(jié)點(diǎn) (定義數(shù)組 )： 首先加入起點(diǎn)， 17 % 7 = 3 擴(kuò)展第 2層結(jié)點(diǎn) (3+5) % 7 = 1 (3 – 5 + 7) % 7 =5 1 2 3 4 5 6 0 + 擴(kuò)展第 3層結(jié)點(diǎn) (1+ 21) % 7 = 1 (1 – 21) % 7 = 1 (5+ 21) % 7 = 5 (5– 21) % 7 = 5 1 2 3 4 5 6 0 擴(kuò)展第 4層結(jié)點(diǎn) (1+ 15) % 7 = 2 (1 – 15) % 7 = 0 (5 + 15) % 7 = 6 (5 – 15) % 7 = 4 1 2 3 4 5 6 0 1 2 3 4 5 6 0 2022/8/21 45 例 3 Holedox Moving ?一條長(zhǎng)度為 L“貪吃蛇”在 n*m的迷宮中，求它走到出口（ 1， 1）的最少步數(shù)。 (2≤L ≤ 8。1n,m ≤ 20) 輸入： 5 6 4 4 1 4 2 3 2 3 1 3 2 3 3 3 3 4 0 0 0 輸出： Case 1: 9 2022/8/21 46 ?蛇頭在上、下、左、右四方向上的探索過程 ?注意： ?蛇不能出界， ?不能撞自己， ?不能撞石頭。 2022/8/21 47 例 4： Eight ? 八數(shù)碼游戲 Input: 2 3 4 1 5 x 7 6 8 Output: ullddrurdllurdruldr 所給輸入為初始狀態(tài)，經(jīng)過移動(dòng)后，終態(tài)是 1 2 3 4 5 6 7 8 x。給出每次移動(dòng)的方向 2022/8/21 48 221786345827364518271634522827 6345123827 6345114687634512787345126152163458782 345817 63164582793145827 617162178634538163547210835427 61816542738135427 6182178634548135624712845621 738154627313813627 4521202178 365452178634511119 八數(shù)碼問題的廣度優(yōu)先搜索 2022/8/21 49 ?分析：所給輸入為初始狀態(tài)，終態(tài)是 1 2 3 4 5 6 7 8 x。 ?將 x當(dāng)作 9，開一個(gè)數(shù)組 a[9！ ]，存每種狀態(tài) ?采取雙向 BFS，前后搜同時(shí)進(jìn)行。 ?初始時(shí)每種狀態(tài)標(biāo)記為 0. 在數(shù)組 a里查找從前邊搜到的狀態(tài)，標(biāo)記是 0， 則置標(biāo)記為 1；標(biāo)記是 1，則說明這是個(gè)前后搜重合狀態(tài)，同時(shí)說明 input有解。 在數(shù)組 a里查找從后邊搜到的狀態(tài)，標(biāo)記是 0，則置為 1；標(biāo)記是 1，則也說明這是個(gè)前后搜重合狀態(tài)，同時(shí)說明 input有解。 2022/8/21 50 BFS練習(xí) ? zju 1091《 Knight Moves》 ? zju 1047《 Image Perimeters》 ? zju 1103《 Hike on a Graph》 ? zju 1649《 Rescue 》 ? zju 1310《 Robot》 ? zju 1136《 Multiple》 ? zju 1530《 Find The Multiple》 ? zju 1301《 The New Villa》 2022/8/21 51 The End. To program is to be error, Just for fun!
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1