LeetCode 286. 墙与门（BFS）
1. 题目
你被给定一个 m × n 的二维网格，网格中有以下三种可能的初始化值：
- -1 表示墙或是障碍物
- 0 表示一扇门
- INF 无限表示一个空的房间。然后，我们用 231 - 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来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/walls-and-gates 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 BFS 超时解
- 对每个点进行BFS，超时
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
if(rooms.size()==0 || rooms[0].size()==0) return;
int INF = INT_MAX, i, j, k,step,size,x,y,nx,ny;
int m = rooms.size(), n = rooms[0].size();
vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
if(rooms[i][j]!=INF)
continue;
vector<vector<bool>> visited(m, vector<bool>(n,false));
visited[i][j] = true;
queue<vector<int>> q;
q.push({i,j});
step = 0;
bool found = false;
while(!q.empty())
{
size = q.size();
while(size--)
{
x = q.front()[0];
y = q.front()[1];
q.pop();
if(rooms[x][y]==0)
{
rooms[i][j] = step;
found = true;
break;
}
for(k = 0; k < 4; ++k)
{
nx = x + dir[k][0];
ny = y + dir[k][1];
if(nx>=0 && nx<m && ny>=0 && ny<n
&& !visited[nx][ny] && rooms[nx][ny] != -1)
{
q.push({nx,ny});
visited[nx][ny] = true;
}
}
}
if(found)
break;
step++;
}
}
}
}
};2.2 从门开始逆向BFS
- 对所有的门同时进行BFS，逆向考虑，每个位置最多访问一次
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
if(rooms.size()==0 || rooms[0].size()==0) return;
int INF = INT_MAX, i, j, k,step = 0,size,x,y,nx,ny;
int m = rooms.size(), n = rooms[0].size();
vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
vector<vector<bool>> visited(m, vector<bool>(n,false));
queue<vector<int>> q;
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
if(rooms[i][j]==0)
{
visited[i][j] = true;
q.push({i,j});
}
}
}
while(!q.empty())
{
size = q.size();
while(size--)
{
x = q.front()[0];
y = q.front()[1];
q.pop();
if(rooms[x][y]==INF)
{
rooms[x][y] = step;
}
for(k = 0; k < 4; ++k)
{
nx = x + dir[k][0];
ny = y + dir[k][1];
if(nx>=0 && nx<m && ny>=0 && ny<n
&& !visited[nx][ny] && rooms[nx][ny] != -1)
{
q.push({nx,ny});
visited[nx][ny] = true;
}
}
}
step++;
}
}
};124 ms 18.8 MB
举报
腾讯云开发者
