C ++中的墙壁和大门

假设我们有一个mxn 2D网格，并使用这三个可能的值进行了初始化。

• -1表示墙壁或障碍物。

• 门为0。

• INF这是无穷大，表示有一个空房间。

在这里2 ^ 31-1 = 2147483647是INF，因为我们可能假设到门的距离小于2147483647。用到其最近门的距离填充每个空房间。如果不可能到达大门，则应填充INF。

所以，如果输入像

那么输出将是

为了解决这个问题，我们将遵循以下步骤-

• 定义大小为4 x 2的数组目录：= {{{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, ],]