สมมติว่าเราต้องการสร้างบ้านบนที่ว่างซึ่งสามารถไปถึงอาคารทั้งหมดด้วยระยะทางรวมน้อยที่สุด เราสามารถเคลื่อนที่ได้ 4 ทิศทาง: บน ล่าง ซ้าย ขวา เรามีกริด 2 มิติค่า 0, 1, 2 โดย:
- 0 แทนที่ว่าง ผ่านได้
- 1 แทนอาคาร ผ่านไม่ได้
- 2 แทนอุปสรรค ผ่านไม่ได้
เช่น ถ้าอินพุตเป็นกริด:
| 1 | 0 | 2 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
ผลลัพธ์จะเป็น 7 เพราะมีอาคาร 3 หลังที่ (0,0), (0,4), (2,2) และอุปสรรคที่ (0,2) จุด (1,2) เป็นที่ว่างที่เหมาะสมที่สุด ระยะทางรวม 3+3+1=7 น้อยที่สุด
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
- ret := inf, n,m ขนาดกริด, numberOfOnes := 0
- สร้างอาร์เรย์ dist และ reach ขนาด n x m
- ลูปทุกเซลล์ ถ้าเป็น 1 (อาคาร): numberOfOnes++; BFS จากจุดนั้น: คำนวณระยะทาง (lvl) ไปยังที่ว่าง (0) อัพเดท dist[nx][ny] += lvl, reach[nx][ny]++
- หลัง BFS ทุกอาคาร: ลูปหาเซลล์ที่เป็น 0 และ reach == numberOfOnes อัพเดท ret = min(ret, dist[i][j])
- คืนค่า ret (ถ้าเป็น inf คืน -1)
ตัวอย่าง
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
class Solution {
public:
int shortestDistance(vector>& grid) {
int ret = INT_MAX;
int n = grid.size(), m = grid[0].size(), numberOfOnes = 0;
vector> dist(n, vector(m)), reach(n, vector(m));
for(int i=0;i> q; q.push({i,j});
set> visited;
for(int lvl=1; !q.empty(); lvl++){
int sz = q.size();
while(sz--){
auto curr = q.front(); q.pop();
int x=curr.first, y=curr.second;
for(int k=0;k<4;k++){
int nx=x+dir[k][0], ny=y+dir[k][1];
if(nx<0||ny<0||nx>=n||ny>=m||visited.count({nx,ny})||grid[nx][ny]!=0) continue;
visited.insert({nx,ny});
dist[nx][ny] += lvl; reach[nx][ny]++;
q.push({nx,ny});
}
}
}
}
for(int i=0;i
อินพุต
[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
เอาต์พุต
7
