ピーク高さ🦖
9105 ワード
説明
あなたは2次元整数matrix
角を含む0
Sと1
s0
○は水を表す1
○は土地を表す.同じ次元の新しい行列を返します.
0
1
隣接するセル間の高さの単位制約
n, m ≤ 250
寂n
○○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;
}
時間複雑度
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;
}
時間複雑度
Reference
この問題について(ピーク高さ🦖), 我々は、より多くの情報をここで見つけました https://dev.to/jiangwenqi/peak-heights-2j13テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol