Càng xa đất càng tốt trong C ++

Giả sử chúng ta có một lưới N x N chỉ chứa các giá trị như 0 và 1, trong đó 0 đại diện cho nước và 1 đại diện cho đất, chúng ta phải tìm một ô nước sao cho khoảng cách của nó đến ô đất gần nhất là lớn nhất và trả về khoảng cách. Ở đây chúng ta sẽ sử dụng khoảng cách Manhattan - khoảng cách giữa hai ô (x0, y0) và (x1, y1) là | x0 - x1 | + | y0 - y1 |. Nếu không có đất hoặc nước trong lưới, hãy trả về -1.

Khi đó đầu ra sẽ là 2, vì ô (1,1) càng xa tất cả vùng đất có khoảng cách 2 càng tốt.

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

• dir:=[(1, 0), (-1, 0), (1, -1), (1, 1), (-1, 1), (-1, -1), (0, 1) , (0, -1)]

• dir2:=[(1, 0), (-1, 0), (0, 1), (0, -1)]

• Xác định một bản đồ m. Xác định một hàng đợi q. n:=số hàng và c:=số cột

• cho tôi trong phạm vi từ 0 đến n - 1

  • cho j trong phạm vi 0 đến n - 1

    • nếu lưới [i, j] là 1, thì hãy chèn một cặp (i, j) vào q và đặt m [(i, j)]:=(j, i)

• ret:=-1

• trong khi q không trống

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

  • trong khi sz không phải là 0

    • temp:=phần tử đầu tiên của q, xóa phần tử đầu tiên khỏi q

    • cho k trong phạm vi 0 đến 3 -

      • nx:=giá trị đầu tiên của temp + dir2 [k, 0]

      • ny:=giá trị thứ hai của temp + dir2 [k, 1]

      • nếu nx và ny không nằm trong phạm vi lưới hoặc lưới [nx, ny] là 1, thì bỏ qua lần lặp tiếp theo.

      • m [(nx, ny)]:=m [temp]

      • ret:=max of (khoảng cách (nx, ny) và m (temp)) và ret

      • insert (nx, ny) vào q

      • đặt lưới [nx, ny]:=1

    • giảm sz đi 1

• trả lại ret

Ví dụ (C ++)

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;
int dir[8][2] = {
   {1, 0}, {-1, 0}, {1, -1}, {1, 1},
   {-1, 1}, {-1, -1}, {0, 1}, {0, -1}
};
int dir2[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
   public:
   int calcDist(int x1, int y1, int x2, int y2){
      return abs(x1 - x2) + abs(y1 - y2);
   }
   int maxDistance(vector<vector<int>>& grid) {
      map < pair <int, int>, pair <int, int> > m;
      queue < pair <int, int> > q;
      int n = grid.size();
      int c = n? grid[0].size() : 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < c; j++){
            if(grid[i][j] == 1){
               q.push({i, j});
               m[{i, j}] = {i, j};
            }
         }
      }
      int ret = -1;
      while(!q.empty()){
         int sz = q.size();
         while(sz--){
            pair <int, int> temp = q.front();
            q.pop();
            for(int k = 0; k < 4; k++){
               int nx = temp.first + dir2[k][0];
               int ny = temp.second + dir2[k][1];
               if(nx < 0 || ny < 0 || nx >= n || ny >= c || grid[nx][ny]) continue;
               m[{nx, ny}] = m[temp];
               ret = max(calcDist(nx, ny, m[temp].first,
               m[temp].second), ret);
               q.push({nx, ny});
               grid[nx][ny] = 1;
            }
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v1 = {{1,0,1},{0,0,0},{1,0,1}};
   Solution ob;
   cout << (ob.maxDistance(v1));
}

Đầu vào

["alice,20,800,mtv","bob,50,1200,mtv"]

Đầu ra

2