피크 하이츠 🦖
설명
matrix
와 0
를 포함하는 2차원 정수 1
가 주어집니다. 여기서 0
는 물을 나타내고 1
는 땅을 나타냅니다. 주어진 다음과 같이 가능한 한 모든 랜드 셀의 높이를 늘리는 동일한 차원의 새 행렬을 반환합니다.
0
1
높이 단위까지 다를 수 있습니다. 적어도 하나의 물 세포가 있다고 가정할 수 있습니다.
제약:
n, m ≤ 250
여기서 n
및 m
는 matrix
의 행 및 열 수입니다.예시 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;
}
시간 복잡도
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.)