forked from fengvyi/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
286. Walls and Gates.cpp
41 lines (38 loc) · 1.59 KB
/
286. Walls and Gates.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
if(rooms.size() == 0 || rooms[0].size() == 0) return;
vector<vector<int>>visited(rooms.size(), vector<int>(rooms[0].size()));
for(int i = 0; i < rooms.size(); i++)
for(int j = 0; j < rooms[0].size(); j++)
if(rooms[i][j] == 0) BFS(rooms, i, j, 0, visited);
}
void BFS(vector<vector<int>>& rooms, int r, int c, int step, vector<vector<int>>& visited){
if(r < 0 || c < 0 || r >= rooms.size() || c >= rooms[0].size() || visited[r][c] || rooms[r][c] < step) return;
if(rooms[r][c] != 0) rooms[r][c] = min(rooms[r][c], step);
visited[r][c] = 1;
BFS(rooms, r - 1, c, step + 1, visited);
BFS(rooms, r + 1, c, step + 1, visited);
BFS(rooms, r, c + 1, step + 1, visited);
BFS(rooms, r, c - 1, step + 1, visited);
visited[r][c] = 0;
}
};
// Further optimize
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
if(rooms.size() == 0 || rooms[0].size() == 0) return;
for(int i = 0; i < rooms.size(); i++)
for(int j = 0; j < rooms[0].size(); j++)
if(rooms[i][j] == 0) BFS(rooms, i, j, 0);
}
void BFS(vector<vector<int>>& rooms, int r, int c, int step){
if(r < 0 || c < 0 || r >= rooms.size() || c >= rooms[0].size() || rooms[r][c] < step) return;
rooms[r][c] = step;
BFS(rooms, r - 1, c, step + 1);
BFS(rooms, r + 1, c, step + 1);
BFS(rooms, r, c + 1, step + 1);
BFS(rooms, r, c - 1, step + 1);
}
};