C++에서 가능한 한 육지에서 멀리

0과 1과 같은 값만 포함하는 하나의 N x N 그리드가 있다고 가정합니다. 여기서 0은 물을 나타내고 1은 토지를 나타냅니다. 가장 가까운 육지 셀까지의 거리가 최대화되도록 물 셀을 찾고 거리를 반환해야 합니다. 여기서 우리는 맨해튼 거리를 사용할 것입니다 - 두 셀 (x0, y0)과 (x1, y1) 사이의 거리는 |x0 - x1| + |y0 - y1|. 그리드에 육지나 물이 없으면 -1을 반환합니다.

그러면 셀 (1,1)이 거리 2인 모든 토지에서 최대한 멀리 떨어져 있으므로 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 디렉토리 :=[(1, 0), (-1, 0), (1, -1), (1, 1), (-1, 1), (-1, -1), (0, 1) , (0, -1)]

• 디렉토리2 :=[(1, 0), (-1, 0), (0, 1), (0, -1)]

• 맵 정의 m. 대기열 q를 정의합니다. n :=행 수 및 c :=열 수

• 0 ~ n – 1 범위의 i에 대해

  • 0 ~ n – 1 범위의 j에 대해

    • grid[i, j]가 1이면 쌍 (i, j)을 q에 삽입하고 m[(i, j)] :=(j,i)

• 렛 :=-1

• q가 비어 있지 않은 동안

  • sz :=q의 크기

  • sz가 0이 아닌 동안

    • temp :=q의 첫 번째 요소, q에서 첫 번째 요소 삭제

    • 범위 0에서 3까지의 k에 대해 -

      • nx :=temp + dir2[k, 0]

        의 첫 번째 값

      • ny :=temp + dir2[k, 1]의 두 번째 값

      • nx 및 ny가 그리드 범위에 있지 않거나 grid[nx, ny]가 1이면 다음 반복으로 건너뜁니다.

      • m[(nx, ny)] :=m[온도]

      • ret :=최대 ((nx, ny) 및 m(temp)의 거리) 및 ret

      • q에 (nx,ny) 삽입

      • 그리드[nx, ny] 설정 :=1

    • sz를 1 감소

• 리턴 렛

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

입력

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

출력

2