01 C++의 행렬

0과 1로 구성된 행렬이 있다고 가정하면 각 셀에 대해 가장 가까운 0의 거리를 찾아야 합니다. 여기서 인접한 두 셀 사이의 거리는 1입니다.

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

그러면 출력은

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

• 크기의 배열 디렉토리 정의:4 x 2 :={{1, 0}, { - 1, 0}, {0, - 1}, {0, 1}}

• n :=행 개수, m :=열 개수

• 하나의 행렬 ret of order(n x m)를 정의하고 inf

  로 채웁니다.

• 하나의 대기열 정의 q

• initialize i :=0의 경우, i

  • j 초기화의 경우:=0, j

    • 행렬[i, j]이 0이 아닌 경우 -

      • ret[i, j] :=0

      • q에 {i, j} 삽입

• initialize lvl :=1의 경우 q가 비어 있지 않으면 업데이트(lvl을 1씩 증가)하고 -

  를 수행합니다.

  • sz :=q의 크기

  • sz가 0이 아닌 동안 각 반복에서 sz를 1씩 줄입니다. -

    • 한 쌍의 curr :=q의 앞 요소 정의

    • q에서 요소 삭제

    • 초기화 k :=0의 경우 k <4일 때 업데이트(k를 1만큼 증가), −

      • nx :=curr.first + dir[k, 0]

      • ny :=curr.second + dir[k, 1]

      • nx <0 또는 nx>=n 또는 ny <0 또는 ny>=m 또는 ret[nx, ny]

        • ret[nx, ny] :=레벨

      • q에 {nx, ny} 삽입

• 리턴 렛

예시

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

#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:
   vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
   int n = matrix.size();
   int m = matrix[0].size();
   vector < vector <int> > ret(n, vector <int>(m, INT_MAX));
   queue < pair <int, int> > q;
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         if(!matrix[i][j]){
            ret[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();
         for(int k = 0; k < 4; k++){
            int nx = curr.first + dir[k][0];
            int ny = curr.second + dir[k][1];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || ret[nx][ny] < lvl) continue;
               ret[nx][ny] = lvl;
               q.push({nx, ny});
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,0},{0,1,0},{1,1,1}};
   print_vector(ob.updateMatrix(v));
}

입력

{{0,0,0},{0,1,0},{1,1,1}}

출력

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