#45183: 廣度優先搜尋yyds(python)


ericcool0705@gmail.com (祥)

學校 : 不指定學校
編號 : 277889
來源 : [106.1.111.157]
最後登入時間 :
2025-01-19 17:11:28
f680. 色塊數量 -- 教學題 | From: [106.1.111.157] | 發表日期 : 2025-01-22 12:20

廣度優先搜尋:

       

  1. 首先將根節點放入佇列中。
  2. 從佇列中取出第一個節點,並檢驗它是否為目標。
    • 如果找到目標,則結束搜尋並回傳結果。
    • 否則將它所有尚未檢驗過的直接子節點加入佇列中。
  3. 若佇列為空,表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋並回傳「找不到目標」。
  4. 重複步驟2。
    BY維基百科

重點:

1.核心想法:利用任一個點,找上下左右的相同色塊,如果找到了就繼續找,完全找不到了就將色塊數量+1

2.建立一個(N+2)*(N+2)的二維陣列,用來記錄哪個色塊被訪問過(陣列裡有-1代表沒訪問過)

   為甚麼是(N+2)*(N+2)原因:

    在找上下左右時,有可能會超出陣列範圍,所以要用一個邊框把N*N框起來,並將邊框設為0(訪問過)。

3.利用deque儲存找到的相同色塊的座標,並利用這個座標繼續上下左右尋找,直到deque變空

   

 

 
ZeroJudge Forum