(Template BFS) LeetCode 286. Walls and Gates

 286. Walls and Gates

You are given an m x n grid rooms initialized with these three possible values.

• -1 A wall or an obstacle.
• 0 A gate.
• INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

 

Example 1:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2:

Input: rooms = [[-1]]
Output: [[-1]]

 

Constraints:

• m == rooms.length
• n == rooms[i].length
• 1 <= m, n <= 250
• rooms[i][j] is -1, 0, or 231 - 1.

	class Solution {
	public:
	void wallsAndGates(vector<vector<int>>& rooms) {
	queue<pair<int, int>> que;
	int m = rooms.size();
	int n = rooms[0].size();
	vector seen(m, vector<bool>(n));
	for(int i = 0; i < m; i++){
	for(int j = 0; j < n; j++){
	if(rooms[i][j] != 0) continue;
	que.emplace(i, j);
	seen[i][j] = true;
	}
	}
	while(!que.empty()){
	auto cur = que.front(); que.pop();
	// 4 side move
	for(int dx = - 1; dx <= 1; dx++){
	for(int dy = - 1; dy <= 1; dy++){
	if(abs(dx + dy) != 1) continue;
	int nx = cur.first + dx;
	int ny = cur.second + dy;
	if(nx >= 0 and nx < m and ny >= 0 and ny < n
	and rooms[nx][ny] != -1 and !seen[nx][ny]){
	// increase moves
	rooms[nx][ny] = rooms[cur.first][cur.second] + 1;
	que.emplace(nx, ny);
	seen[nx][ny] = true;
	}
	}
	}
	}
	}
	};

view raw 286. Walls and Gates hosted with ❤ by GitHub