สมมติว่ามีกริด 2 มิติขนาด m x n ที่เริ่มต้นด้วยค่าที่เป็นไปได้สามค่า
-1 สำหรับกำแพงหรืออุปสรรค
0 สำหรับประตู
INF หมายถึงอนันต์ คือห้องว่าง
ที่นี่ 2^31 - 1 = 2147483647 คือ INF เนื่องจากเราสมมติได้ว่าระยะทางไปประตูน้อยกว่า 2147483647 เติมแต่ละห้องว่างด้วยระยะทางไปประตูที่ใกล้ที่สุด หากไปไม่ถึงประตู ให้เติมด้วย INF
เช่น ถ้าอินพุทเป็น
| INF | -1 | 0 | INF |
| INF | INF | INF | -1 |
| INF | -1 | INF | -1 |
| 0 | -1 | INF | INF |
ผลลัพธ์จะเป็น
| 3 | -1 | 0 | 1 |
| 2 | 2 | 1 | -1 |
| 1 | -1 | 2 | -1 |
| 0 | -1 | 3 | 4 |
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดอาร์เรย์ dir ขนาด 4 x 2 := {{1, 0}, {-1, 0}, {0, 1}, {0,-1}}
n := ขนาดของ rooms
m := (ถ้า n ไม่เป็นศูนย์ แล้วจำนวนคอลัมน์ มิฉะนั้น 0)
กำหนดคิว q ของ pairs
ลูป i := 0 ถึง n-1 ทำ −
ลูป j := 0 ถึง m-1 ทำ −
ถ้า rooms[i][j] เท่ากับ 0 แล้ว −
แทรก { i, j } ลงใน q
ลูป lvl := 1 ถึง q ไม่ว่าง เพิ่ม lvl ทุกครั้ง ทำ −
sz := ขนาดของ q
ลูป while sz ไม่เป็นศูนย์ ลด sz ลง 1 ทุกครั้ง ทำ −
กำหนด pair curr := สมาชิกแรกของ q
ลบสมาชิกออกจาก q
x := curr.first
y := curr.second
ลูป i := 0 ถึง 3 ทำ −
nx := x + dir[i][0]
ny := y + dir[i][1]
ถ้า nx < 0 หรือ ny < 0 หรือ nx >= n หรือ ny >= m หรือ rooms[nx][ny] < lvl แล้ว −
ข้ามส่วนต่อไป ไปรอบถัดไป
rooms[nx][ny] := lvl
แทรก { nx, ny } ลงใน q
ตัวอย่าง
ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; class Solution { public: void wallsAndGates(vector<vector<int>>& rooms) { int n = rooms.size(); int m = n ? rooms[0].size() : 0; queue<pair<int, int> > q; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (rooms[i][j] == 0) q.push({ i, j }); } } for (int lvl = 1; !q.empty(); lvl++) { int sz = q.size(); while (sz--) { pair<int, int> curr = q.front(); q.pop(); int x = curr.first; int y = curr.second; for (int i = 0; i < 4; i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; if (nx < 0 || ny < 0 || nx >= n || ny >= m || rooms[nx][ny] < lvl) continue; rooms[nx][ny] = lvl; q.push({ nx, ny }); } } } } }; main(){ vector<vector<int>> v = {{2147483647,-1,0,2147483647}, {2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1}, {0,-1,2147483647,2147483647}}; Solution ob; ob.wallsAndGates(v); print_vector(v); } อินพุท
{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}} เอาต์พุท
[[3, -1, 0, 1, ],[2, 2, 1, -1, ],[1, -1, 2, -1, ],[0, -1, 3, 4, ],]
