【筆記】BFS (Breadth First Search，廣度優先搜尋) - Yui ...

【筆記】BFS (Breadth First Search，廣度優先搜尋) · 每拜訪一個鄰居，就一併把可行「鄰居的鄰居」加入queue的尾端。

距離要加上1。

· 拜訪過所有可通行的點 ... SkiptocontentSkiptoblogsidebar 參考基礎圖論【筆記】【用途】在樹(tree)或圖(graph)上找出從特定起點出發，抵達指定終點的最短距離(shortestpath)。

【觀念】利用queue資料先進先出的特性來確保「先被搜尋到的頂點，會先成為下一個搜尋起點」。

【實作】以queue方式實現。

【筆記】【範例】ZeroJudged453:三、最短距離【題解】利用BFS(BreadstFirstSearch，廣度優先搜尋)找出起點與終點間的最短距離。

每個座標點的距離初始值設為0或-1，順便當成這個點是否搜索過的flag。

從起點開始檢查上下左右四個座標，把能通行的「最近」而且「還沒拜訪過」的鄰居點加進queue。

這些直接鄰居們的距離要加上1。

每拜訪一個鄰居，就一併把可行「鄰居的鄰居」加入queue的尾端。

距離要加上1。

拜訪過所有可通行的點之後，就可計算出從起點到這些點之間的最短距離。

#include #include #include usingnamespacestd; intmain(){ intnum,n,m,sx,sy,tx,ty; while(cin>>num){ for(intiter=0;iter>n>>m>>sx>>sy>>tx>>ty; sx--; sy--; tx--; ty--; inta[n][m]; intdx[4]={0,0,1,-1}; intdy[4]={1,-1,0,0}; stringstr; for(intj=0;j>str; for(intk=0;k>q; q.push({sx,sy}); arr[sx][sy]=1; while(!q.empty()){ pairnow; now=q.front(); q.pop(); for(inti=0;i<4;i++){ if(now.first+dx[i]>=0&&now.first+dx[i]=0&&now.second+dy[i]