#40930: C++詳解-BFS+Map


toseanlin@gmail.com (Dr. SeanXD)

學校 : 康橋雙語學校
編號 : 158065
來源 : [24.147.249.5]
最後登入時間 :
2024-10-28 09:54:40
o077. 2. 電子畫布 -- 2024年6月APCS | From: [220.136.87.155] | 發表日期 : 2024-06-19 12:06

使用 BFS 的方式來畫畫,終止條件除了當沒有起點時,當跑 BFS 的次數 >= T 時也要終止,曼哈頓距離其實就是走了幾步的意思,也就是 BFS 跑的次數。

在 BFS 的參數中需要有一個 map 來存取已經走過哪些點了,這邊取名叫做 all,如果 all[現在座標] == 0 才能給目前座標加上 X,並且每次走到任何座標都需要 all[座標]++,因為在同樣的第 N 次 BFS 中,同一個點只能被加一次 X,不能累加

另外,為了避免超時,可以宣告一個 map 來存取下一次 BFS 已經有的起點,這邊取名叫做 add。當新增了下一次 BFS 的起點時,add[座標]++,並且要新增時需要判斷 add[座標] 是否為 0,如果是 0 才要新增這個座標。

 

範例程式碼

 
ZeroJudge Forum