이진 행렬이 주어지면 각 셀에서 1을 포함하는 가장 가까운 셀까지의 최소 거리를 찾아야 합니다.
예를 들어 보겠습니다.
입력
0 0 1 1 1 0 0 0 0
출력
1 1 0 0 0 1 1 1 2
최소 거리는 현재 셀 행 - 1 셀 행 + 현재 셀 열 - 1 셀 열에서 최소 거리입니다.
알고리즘
-
원하는 크기의 행렬을 초기화합니다.
-
거리를 저장하기 위해 동일한 크기의 다른 행렬을 초기화합니다.
-
전체 행렬에 대해 반복
.-
현재 셀 값이 1이면 1에서 1까지의 거리가 0이므로 거리를 0으로 설정
-
현재 셀 값이 0인 경우
-
전체 행렬을 다시 반복합니다.
-
셀이 1이면 현재 셀과의 거리를 계산합니다.
-
최소 거리를 업데이트하십시오.
.
-
-
-
거리 행렬을 인쇄합니다.
구현
다음은 위의 알고리즘을 C++로 구현한 것입니다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> findNearest1Distance(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (rows == 0) {
return matrix;
}
int cols = matrix[0].size();
vector<vector<int>> distance(rows, vector<int>(cols, INT_MAX));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
distance[i][j] = 0;
}else if (matrix[i][j] == 0) {
for (int k = 0; k < rows; k++) {
for (int l = 0; l < cols; l++) {
if (matrix[k][l] == 1) {
distance[i][j] = min(distance[i][j], abs(k - i) + abs(l - j));
}
}
}
}
}
}
return distance;
}
int main() {
vector<vector<int>> matrix{
{0, 0, 1},
{1, 1, 0},
{0, 0, 0}
};
vector<vector<int>> result = findNearest1Distance(matrix);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
1 1 0 0 0 1 1 1 2