C ++中的墙壁和大门
假设我们有一个mxn2D网格，并使用这三个可能的值进行了初始化。
-1表示墙壁或障碍物。
门为0。
INF这是无穷大，表示有一个空房间。
在这里2^31-1=2147483647是INF，因为我们可能假设到门的距离小于2147483647。用到其最近门的距离填充每个空房间。如果不可能到达大门，则应填充INF。
所以，如果输入像
那么输出将是
为了解决这个问题，我们将遵循以下步骤-
定义大小为4x2的数组目录：={{{1，0}，{-1，0}，{0，1}，{0，-1}}
n：=房间大小
m：=（如果n为非零，则为列数，否则为0）
定义一对队列q
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
如果rooms[i，j]等于0，则-
将{i，j}插入q
对于初始化j：=0，当j<m时，更新（将j增加1），执行-
对于初始化lvl：=1，当非q为空时，更新（将lvl增加1），执行-
定义一对curr：=q的第一个元素
从q删除元素
x：=curr.first
y：=curr.second
对于初始化i：=0，当i<4时，更新（将i增加1），请执行-
忽略以下部分，跳至下一个迭代
nx：=x+dir[i，0]
ny：=y+dir[i，1]
如果nx<0或ny<0或nx>=n或ny>=m或rooms[nx，ny]<lvl，则-
rooms[nx，ny]：=lvl
将{nx，ny}插入q
sz：=q的大小
当sz为非零值时，请在每次迭代中将sz减1，然后执行-
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto< > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
void wallsAndGates(vector<vector<int<>& rooms) {
int n = rooms.size();
int m = n ? rooms[0].size() : 0;
queue<pair<int, int> > q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (rooms[i][j] == 0)
q.push({ i, j });
}
}
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
pair<int, int> curr = q.front();
q.pop();
int x = curr.first;
int y = curr.second;
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || rooms[nx][ny] < lvl)
continue;
rooms[nx][ny] = lvl;
q.push({ nx, ny });
}
}
}
}
};
main(){
vector<vector<int<> v = {{2147483647,-1,0,2147483647}, {2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1}, {0,-1,2147483647,2147483647}};
Solution ob;
ob.wallsAndGates(v);
print_vector(v);
}输入项
{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}}输出结果
[[3, -1, 0, 1, ],[2, 2, 1, -1, ],[1, -1, 2, -1, ],[0, -1, 3, 4, ],]