C++의 모든 건물에서 최단 거리

<시간/>

모든 건물에 최단거리로 도달할 수 있는 빈 땅에 집을 짓고 싶다고 가정해 봅시다. 상하좌우 4방향만 움직일 수 있습니다. 0, 1 또는 2 값의 2D 그리드가 있습니다. 여기서 -

0은 우리가 자유롭게 지나갈 수 있는 빈 땅을 나타냅니다.
1은 통과할 수 없는 건물을 나타냅니다.
2는 우리가 통과할 수 없는 장애물을 나타냅니다.

따라서 입력이 다음과 같으면

1	2	1
0	0	0
0	1	0

세 개의 건물이 (0,0), (0,4), (2,2)에 있고 장애물이 (0,2)에 있으므로 출력은 7이므로 점 (1,2)는 총 이동 거리가 3+3+1=7이 최소이므로 집을 짓기에 이상적인 빈 땅입니다.

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

ret :=inf
n :=그리드의 행 크기
m :=그리드의 열 크기
numberOfOnes :=0
n x m 크기의 2D 배열 dist 하나 정의
크기가 n x m인 하나의 2D 어레이 범위 정의
initialize i :=0의 경우, i
- j 초기화의 경우:=0, j
  - grid[i, j]가 1과 같으면 -
    - (numberOfOnes 1씩 증가)
    - 하나의 대기열 정의 q
    - q에 {i, j} 삽입
    - 방문한 한 세트 정의
    - initialize lvl :=1의 경우 q가 비어 있지 않으면 업데이트(lvl을 1씩 증가)하고 -
      를 수행합니다.
      - sz :=q의 크기
      - sz가 0이 아닌 동안 각 반복에서 sz를 감소시키고 -
        
        curr :=q의 첫 번째 요소
        
        q에서 요소 삭제
        
        x :=curr.first
        
        y :=curr.second
        
        초기화 k :=0의 경우 k <4일 때 업데이트(k를 1만큼 증가), −
        
        nx :=x + dir[k, 0]
        
        ny :=y + dir[k, 1]
        
        nx와 ny가 그리드 orgrid[nx,ny]의 범위에 있으면 0이 아니면
        
        다음 부분은 무시하고 다음 반복으로 건너뛰십시오.
        
        {nx, ny}를 방문
        에 삽입
        
        dist[nx, ny] :=dist[nx, ny] + 레벨
        
        (도달[nx, ny] 1 증가)
        
        q에 {nx, ny} 삽입
initialize i :=0의 경우, i
- j 초기화의 경우:=0, j
  - grid[i, j]가 0과 같고 Reach[i, j]가 numberOfOnes와 같으면 -
    - ret :=ret 및 dist[i, j]의 최소값
return (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]]