ピーク高さ🦖


説明


あなたは2次元整数matrix 角を含む0 Sと1 s0 ○は水を表す1 ○は土地を表す.同じ次元の新しい行列を返します.
  • どのような水セルの高さも0
  • どんな細胞でも、最もわずかに1 隣接するセル間の高さの単位
  • 少なくとも1つの水セルがあると仮定できます.
    制約
  • n, m ≤ 250n ○○m ○は1行あたりの列数、matrix
  • 例1


    入力


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

    出力


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

    直観


    …するmulti source BFS すべての水の位置からI . E ' 0は、すべてのそのようなセルをキューに挿入することによって

    実装


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

    時間複雑度

  • time : o ( n )
  • space : o ( n )