Khoảng cách ngắn nhất từ ​​tất cả các tòa nhà trong C ++

Giả sử chúng ta muốn tạo một ngôi nhà trên một khu đất trống mà có thể tiếp cận tất cả các tòa nhà trong một khoảng cách ngắn nhất. Chúng ta chỉ có thể di chuyển bốn hướng như lên, xuống, trái và phải. Chúng tôi có lưới 2D gồm các giá trị 0, 1 hoặc 2, trong đó -

• 0 đại diện cho một vùng đất trống mà chúng ta có thể đi qua một cách tự do.

• 1 đại diện cho một tòa nhà mà chúng ta không thể đi qua.

• 2 đại diện cho một chướng ngại vật mà chúng ta không thể vượt qua.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 7 vì Cho ba tòa nhà có mặt tại (0,0), (0,4), (2,2) và một chướng ngại vật ở (0,2) nên điểm (1,2) là một khu đất trống lý tưởng để xây nhà vì tổng quãng đường di chuyển là 3 + 3 + 1 =7 là tối thiểu.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=inf

• n:=kích thước hàng của lưới

• m:=kích thước col của lưới

• numberOfOnes:=0

• Xác định một phân vùng mảng 2D có kích thước n x m

• Xác định phạm vi tiếp cận của một mảng 2D có kích thước n x m

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j

    • nếu lưới [i, j] giống 1, thì -

      • (tăng numberOfOnes lên 1)

      • Xác định một hàng đợi q

      • chèn {i, j} vào q

      • Xác định một tập hợp đã truy cập

      • để khởi tạo lvl:=1, khi không phải q trống, hãy cập nhật (tăng lvl lên 1), thực hiện -

        • sz:=kích thước của q

        • trong khi sz khác 0, giảm sz trong mỗi lần lặp, thực hiện -

          • curr:=phần tử đầu tiên của q

          • xóa phần tử khỏi q

          • x:=curr.first

          • y:=curr.second

          • để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện -

            • nx:=x + dir [k, 0]

            • ny:=y + dir [k, 1]

            • nếu nx và ny nằm trong phạm vi lưới tổ chức [nx, ny] không phải là 0 thì

            • Bỏ qua phần sau, bỏ qua phần tiếp theo

            • chèn {nx, ny} vào đã truy cập

            • dist [nx, ny]:=dist [nx, ny] + lvl

            • (tăng phạm vi tiếp cận [nx, ny] lên 1)

            • chèn {nx, ny} vào q

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j

    • nếu lưới [i, j] giống 0 và phạm vi tiếp cận [i, j] giống numberOfOnes, thì -

      • ret:=tối thiểu ret và dist [i, j]

• return (nếu ret giống với inf thì -1, ngược lại là ret)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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;
   }
};

Đầu vào

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

Đầu ra

7