2차원 행렬이 있다고 가정하고 모든 요소가 동일한 값을 포함하는 가장 큰 k × k 부분행렬을 찾은 다음 k 값을 찾아야 합니다.
따라서 입력이 다음과 같으면
| 1 | 1 | 8 | 3 |
| 1 | 5 | 5 | 5 |
| 2 | 5 | 5 | 5 |
| 4 | 5 | 5 | 5 |
값이 5인 3 × 3 정방 행렬이 있으므로 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=행렬의 행 수
-
m :=행렬의 열 개수
-
크기(n x m)의 하나의 2D 배열 dp를 정의하고 1로 채웁니다.
-
렛 :=1
-
초기화 i :=n - 1의 경우, i>=0일 때 업데이트(i를 1만큼 감소), −
-
j 초기화의 경우 :=m - 1, j>=0일 때 업데이트(j를 1만큼 감소), −
-
발 :=inf
-
i + 1
-
val :=dp[i + 1, j] 및 val
의 최소값
-
-
그렇지 않으면
-
값 :=0
-
-
j + 1
-
val :=dp[i, j + 1] 및 val
의 최소값
-
-
그렇지 않으면
-
값 :=0
-
-
i + 1
-
val :=dp[i + 1, j + 1] 및 val
의 최소값
-
-
그렇지 않으면
-
값 :=0
-
-
val이 inf와 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
dp[i, j] :=dp[i, j] + 발
-
ret :=ret 및 dp[i, j]
의 최대값
-
-
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>>& v) {
int n = v.size();
int m = v[0].size();
vector<vector<int>> dp(n, vector<int>(m, 1));
int ret = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
int val = INT_MAX;
if (i + 1 < n && v[i + 1][j] == v[i][j]) {
val = min(dp[i + 1][j], val);
}
else {
val = 0;
}
if (j + 1 < m && v[i][j + 1] == v[i][j]) {
val = min(dp[i][j + 1], val);
}
else {
val = 0;
}
if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) {
val = min(dp[i + 1][j + 1], val);
}
else {
val = 0;
}
if (val == INT_MAX)
continue;
dp[i][j] += val;
ret = max(ret, dp[i][j]);
}
}
return ret;
}
};
int solve(vector<vector<int>>& matrix) {
return (new Solution())->solve(matrix);
}
int main(){
vector<vector<int>> matrix = {
{1, 1, 8, 3},
{1, 5, 5, 5},
{2, 5, 5, 5},
{4, 5, 5, 5}
};
cout << solve(matrix);
} 입력
{ {1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5,
5} }; 출력
3