与C ++中所有建筑物的最短距离

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们要在空旷的土地上建造一所房屋，该房屋要以最短的距离到达所有建筑物。我们只能向上，向下，向左和向右四个方向移动。我们有一个值为0、1或2的2D网格，其中-

  • 0代表我们可以自由经过的空地。

  • 1代表我们无法通过的建筑物。

  • 2代表我们无法通过的障碍。

所以，如果输入像

10201
00000
00100

则输出将为7，因为给定三栋建筑物位于(0,0)，(0,4)，(2,2)，并且障碍物位于(0,2)，因此点(1,2)为理想的空地来盖房，因为总行驶距离为3 + 3 + 1 = 7最小。

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

  • ret：= inf

  • n：=网格的行大小

  • m：=网格的col大小

  • numberOfOnes：= 0

  • 定义大小为nxm的2D数组dist

  • 定义一个尺寸为nxm的2D阵列范围

  • 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

    • 如果grid [i，j]与1相同，则-

    • sz：= q的大小

    • 当sz为非零值时，请在每次迭代中减少sz，请执行-

    • nx：= x + dir [k，0]

    • ny：= y + dir [k，1]

    • 如果nx和ny在grid的范围内，或者grid [nx，ny]不为0，则

    • 忽略以下部分，跳至下一个迭代

    • 将{nx，ny}插入访问

    • dist [nx，ny]：= dist [nx，ny] + lvl

    • （将覆盖率[nx，ny]增加1）

    • 将{nx，ny}插入q

    • curr：= q的第一个元素

    • 从q删除元素

    • x：= curr.first

    • y：= curr.second

    • 对于初始化k：= 0，当k <4时，更新（将k增加1），执行-

    • （将numberOfOnes增加1）

    • 定义一个队列q

    • 将{i，j}插入q

    • 定义一组参观

    • 对于初始化lvl：= 1，当非q为空时，更新（将lvl增加1），执行-

    • 对于初始化j：= 0，当j <m时，更新（将j增加1），执行-

    • 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

      • 如果grid [i，j]与0相同，而reach [i，j]与numberOfOnes相同，则-

      • ret：= ret和dist [i，j]的最小值

      • 对于初始化j：= 0，当j <m时，更新（将j增加1），执行-

      • 返回（如果ret与inf相同，则为-1，否则为ret）

      例  

      让我们看下面的实现以更好地理解-

      int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
      class Solution {
      public:
         int shortestDistance(vector<vector<int>>& grid) {
            int ret = INT_MAX;
            int n = grid.size();
            int m = grid[0].size();
            int numberOfOnes = 0;
            vector < vector <int> > dist(n, vector <int>(m));
            vector < vector <int> > reach(n, vector <int>(m));
            for(int i = 0; i < n; i++){
               for(int j = 0; j < m; j++){
                  if(grid[i][j] == 1){
                     numberOfOnes++;
                     queue < pair <int, int> > q;
                     q.push({i, j});
                     set < pair <int, int> > visited;
                     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 k = 0; k < 4; k++){
                              int nx = x + dir[k][0];
                              int ny = y + dir[k][1];
                              if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0) continue;
                              visited.insert({nx, ny});
                              dist[nx][ny] += lvl;
                              reach[nx][ny]++;
                              q.push({nx, ny});
                           }
                        }
                     }
                  }
               }
            }
            for(int i = 0; i < n; i++){
               for(int j = 0; j < m; j++){
                  if(grid[i][j] == 0 && reach[i][j] == numberOfOnes){
                     ret = min(ret, dist[i][j]);
                  }
               }
            }
            return ret == INT_MAX ? -1 : ret;
         }
      };

      输入值

      [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

      输出结果

      7

      以上是 与C ++中所有建筑物的最短距离 的全部内容， 来源链接： utcz.com/z/317061.html

      回到顶部