피크 하이츠 🦖

설명


matrix0를 포함하는 2차원 정수 1가 주어집니다. 여기서 0는 물을 나타내고 1는 땅을 나타냅니다. 주어진 다음과 같이 가능한 한 모든 랜드 셀의 높이를 늘리는 동일한 차원의 새 행렬을 반환합니다.
  • 워터 셀 스테이의 높이0
  • 모든 셀은 인접한 셀(위, 아래, 왼쪽, 오른쪽) 사이의 최대 1 높이 단위까지 다를 수 있습니다.

  • 적어도 하나의 물 세포가 있다고 가정할 수 있습니다.

    제약:
  • n, m ≤ 250 여기서 nmmatrix의 행 및 열 수입니다.

  • 예시 1



    입력




    matrix = [
        [0, 1, 0],
        [1, 1, 1],
        [1, 1, 1]
    ]
    


    산출




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



    직관



    이러한 모든 셀을 대기열에 삽입하여 모든 물 위치(예: 0)에서 수행multi source BFS

    구현




    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    
    vector<vector<int>> solve(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        queue<pair<int, int>> q;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) q.push({i, j});
            }
        }
        int val = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto point = q.front();
                q.pop();
                if (visited[point.first][point.second]) continue;
                visited[point.first][point.second] = true;
                matrix[point.first][point.second] = val;
                for (int j = 0; j < 4; j++) {
                    int x = point.first + dx[j], y = point.second + dy[j];
                    if (x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y]) q.push({x, y});
                }
            }
            val++;
        }
        return matrix;
    }
    


    시간 복잡도


  • 시간: O(n)
  • 스페이스: O(n)
  • 좋은 웹페이지 즐겨찾기