文章目录
1. 题目2. 解题2.1 BFS 超时解2.2 从门开始逆向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
长按或扫码关注我的公众号，一起加油、一起学习进步！
