542. 01 행렬
0 과 1 로 구 성 된 행렬 을 지정 하여 각 요소 에서 가장 가 까 운 0 까지 의 거 리 를 찾 습 니 다.
두 인접 원소 간 의 거 리 는 1 이다.
예제 1: 입력:
0 0 0
0 1 0
0 0 0
출력:
0 0 0
0 1 0
0 0 0
예제 2: 입력:
0 0 0
0 1 0
1 1 1
출력:
0 0 0
0 1 0
1 2 1
주의:
주어진 행렬 의 요소 개 수 는 10000 을 초과 하지 않 습 니 다.주어진 행렬 에 적어도 하나의 요 소 는 0 이다.행렬 중의 요 소 는 네 가지 방향 에서 만 인접 한다. 위, 아래, 왼쪽, 오른쪽 이다.
분석 하 다.
BFS 알고리즘 을 사용 하여 첫 번 째 단 계 는 행렬 을 옮 겨 다 니 며 모든 0 값 이 출발점 일 수 있 습 니 다. 대기 열 에 저장 하고 0 값 이 아 닌 INT 로 설정 합 니 다.MAX 두 번 째 단 계 는 대기 열 을 옮 겨 다 니 며 대기 열 머리의 점, x, y 를 가 져 옵 니 다.위, 아래, 왼쪽, 오른쪽 점 을 판단 하고 matrix [x] [y] + 1 보다 크 면 이 점 들 의 수 치 를 업데이트 하고 업 데 이 트 된 점 을 대기 열 에 넣 습 니 다. 이 점 들 이 업데이트 되 었 기 때문에 이 점 들 주위 의 점 들 도 업데이트 가 필요 할 수 있 습 니 다.
코드
class Solution {
public:
vector> updateMatrix(vector>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
queue> q;
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
if(matrix[i][j] == 0) {
q.push(make_pair(i, j));
} else {
matrix[i][j] = INT_MAX;
}
}
}
while(!q.empty()){
auto p = q.front();
int x = p.first;
int y = p.second;
q.pop();
int cur = matrix[x][y] + 1;
if(x > 0 && matrix[x - 1][y] > cur) {
matrix[x-1][y] = cur;
q.push(make_pair(x - 1, y));
}
if(x < row - 1 && matrix[x + 1][y] > cur) {
matrix[x + 1][y] = cur;
q.push(make_pair(x + 1, y));
}
if(y > 0 && matrix[x][y - 1] > cur) {
matrix[x][y - 1] = cur;
q.push(make_pair(x, y - 1));
}
if(y < col - 1 && matrix[x][y + 1] > cur) {
matrix[x][y + 1] = cur;
q.push(make_pair(x, y + 1));
}
}
return matrix;
}
};
제목 링크
https://leetcode-cn.com/problems/01-matrix/description/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.