数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：查找给定矩阵中 kxk 大小的相同值方阵
假设我们有一个二维矩阵，我们需要找到其中所有元素都相同值的最大 kxk 子矩阵，然后找到 k 的值。
例如，如果输入如下：
| 1 | 1 | 8 | 3 |
| 1 | 5 | 5 | 5 |
| 2 | 5 | 5 | 5 |
| 4 | 5 | 5 | 5 |
则输出为 3，因为存在一个 3x3 的值为 5 的方阵。
为了解决这个问题，我们将遵循以下步骤：
n := 矩阵的行数
m := 矩阵的列数
定义一个大小为 (nxm) 的二维数组 dp 并将其填充为 1
ret := 1
初始化 i := n - 1，当 i >= 0 时，更新 (i 减 1)，执行：
初始化 j := m - 1，当 j >= 0 时，更新 (j 减 1)，执行：
val := inf
如果 i + 1 < n 且 v[i + 1, j] 与 v[i, j] 相同，则：
val := dp[i + 1, j] 和 val 的最小值
否则
val := 0
如果 j + 1 < m 且 v[i, j + 1] 与 v[i, j] 相同，则：
val := dp[i, j + 1] 和 val 的最小值
否则
val := 0
如果 i + 1 < n 且 j + 1 < m 且 v[i + 1, j + 1] 与 v[i, j] 相同，则：
val := dp[i + 1, j + 1] 和 val 的最小值
否则
val := 0
如果 val 等于 inf，则：
忽略以下部分，跳到下一个迭代
dp[i, j] := dp[i, j] + val
ret := ret 和 dp[i, j] 的最大值
返回 ret
示例
让我们来看下面的实现以更好地理解：
#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
更新于：2020-12-23
浏览量：121
广告