Tường và Cổng trong C ++

Giả sử chúng ta có một lưới 2D m x n và lưới đó được khởi tạo với ba giá trị có thể có sau.

• -1 cho một bức tường hoặc một chướng ngại vật.

• 0 cho một cổng.

• INF Đây là vô cực có nghĩa là một căn phòng trống.

Ở đây 2 ^ 31 - 1 =2147483647 là INF vì chúng ta có thể giả định rằng khoảng cách đến cổng nhỏ hơn 2147483647. Hãy lấp đầy mỗi phòng trống bằng khoảng cách đến cổng gần nhất. Nếu không thể đến được cổng, nó nên được điền đầy đủ thông tin vào INF.

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

thì đầu ra sẽ là

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

• Xác định dir mảng có kích thước:4 x 2:={{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

• n:=kích thước của phòng

• m:=(nếu n khác 0 thì đếm cột, ngược lại là 0)

• Xác định một hàng đợi q trong số các cặp

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

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

    • nếu các phòng [i, j] bằng 0 thì -

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

• để 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 đi 1 trong mỗi lần lặp, thực hiện -

    • Xác định một cặp 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 i:=0, khi i <4, cập nhật (tăng i lên 1), thực hiện -

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

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

      • nếu nx <0 hoặc ny <0 hoặc nx> =n hoặc ny> =m hoặc phòng [nx, ny]

        • Bỏ qua phần sau, chuyển sang phần tiếp theo

      • phòng [nx, ny]:=lvl

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

Ví dụ

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

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

Đầu vào

{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}}

Đầu ra

[[3, -1, 0, 1, ],[2, 2, 1, -1, ],[1, -1, 2, -1, ],[0, -1, 3, 4, ],]