के को खोजने के लिए कार्यक्रम जहां दिए गए मैट्रिक्स में सी ++ में समान मूल्य के के द्वारा के वर्ग है

मान लीजिए कि हमारे पास 2d मैट्रिक्स है, हमें सबसे बड़ा k × k सबमैट्रिक्स खोजना है, जहां इसके सभी तत्वों का मान समान है, तो k का मान ज्ञात करें।

तो, अगर इनपुट पसंद है

1	1	8	3
1	5	5	5
2	5	5	5
4	5	5	5

तो आउटपुट 3 होगा, क्योंकि मान 5 का 3 × 3 वर्ग मैट्रिक्स है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=मैट्रिक्स की पंक्ति गणना
मी :=मैट्रिक्स की कॉलम संख्या
एक 2D सरणी dp आकार (n x m) परिभाषित करें और 1
. से भरें
रिट :=1
इनिशियलाइज़ करने के लिए i :=n-1, जब i>=0, अपडेट करें (i से 1 घटाएं), −
करें
- प्रारंभ करने के लिए j :=m-1, जब j>=0, अद्यतन करें (j को 1 से घटाएं), करें -
  - वैल:=inf
  - यदि i + 1
    - वैल:=न्यूनतम डीपी[i + 1, j] और वैल
  - अन्यथा
    - वैल:=0
  - यदि j + 1
    - वैल:=न्यूनतम डीपी[i, j + 1] और वैल
  - अन्यथा
    - वैल:=0
  - यदि i + 1
    - वैल:=न्यूनतम डीपी[i + 1, j + 1] और वैल
  - अन्यथा
    - वैल:=0
  - अगर वैल inf के समान है, तो -
    - निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
  - डीपी [आई, जे]:=डीपी [आई, जे] + वैल
    - रिट :=अधिकतम रिट और डीपी[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} };