你被给定一个 m × n 的二维网格,网格中有以下三种可能的初始化值:
你要给每个空房间位上填上该房间到 最近 门的距离,如果无法到达门,则填 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
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++;
}
}
}
}
};
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