Chương trình tìm k trong đó ma trận đã cho có k bằng k bình phương cùng giá trị trong C ++

Giả sử chúng ta có một ma trận 2d, chúng ta phải tìm ma trận con k × k lớn nhất mà tất cả các phần tử của nó đều chứa cùng một giá trị, sau đó tìm giá trị của k.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 3, vì có một ma trận vuông 3 × 3 có giá trị là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=số hàng của ma trận

• m:=số cột của ma trận

• Xác định một dp mảng 2D có kích thước (n x m) và điền bằng 1

• ret:=1

• để khởi tạo i:=n - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

  • để khởi tạo j:=m - 1, khi j> =0, cập nhật (giảm j đi 1), thực hiện -

    • val:=inf

    • nếu i + 1

      • val:=tối thiểu của dp [i + 1, j] và val

    • Nếu không

      • val:=0

    • nếu j + 1

      • val:=tối thiểu của dp [i, j + 1] và val

    • Nếu không

      • val:=0

    • nếu i + 1

      • val:=tối thiểu của dp [i + 1, j + 1] và val

    • Nếu không

      • val:=0

    • nếu val giống với inf, thì -

      • Bỏ qua phần sau, chuyển sang phần tiếp theo

    • dp [i, j]:=dp [i, j] + val

      • ret:=tối đa ret và dp [i, j]

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

{ {1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5,
5} };

Đầu ra

3