โปรแกรมหาขนาด k ของเมทริกซ์ย่อย k×k ที่มีค่าเท่ากันทุกเซลล์ใน C++

สมมติว่าเรามีเมทริกซ์ 2 มิติ เราต้องการหาค่า k ที่มากที่สุด ซึ่งมีเมทริกซ์ย่อยขนาด k×k ที่ทุกองค์ประกอบมีค่าเท่ากัน

ตัวอย่างเช่น หากอินพุตเป็นเมทริกซ์:

ผลลัพธ์จะเป็น 3 เนื่องจากมีเมทริกซ์ย่อย 3×3 ที่มีค่าเป็น 5 ทุกเซลล์

ขั้นตอนการแก้ปัญหา

1. n := จำนวนแถวของเมทริกซ์, m := จำนวนคอลัมน์
2. สร้างอาร์เรย์ dp ขนาด n×m เริ่มต้นทุกค่าเป็น 1
3. ret := 1
4. วนลูปจากด้านล่างขวาไปด้านบนซ้าย (i จาก n-1 ถึง 0, j จาก m-1 ถึง 0):
   • val := infinity
   • ตรวจสอบเซลล์ด้านล่าง (i+1, j): ถ้าค่าเท่ากับเซลล์ปัจจุบัน ให้ val = min(val, dp[i+1][j]) มิฉะนั้น val = 0
   • ตรวจสอบเซลล์ด้านขวา (i, j+1): ถ้าค่าเท่ากัน val = min(val, dp[i][j+1]) มิฉะนั้น val = 0
   • ตรวจสอบเซลล์แนวทแยง (i+1, j+1): ถ้าค่าเท่ากัน val = min(val, dp[i+1][j+1]) มิฉะนั้น val = 0
   • ถ้า val ยังคงเป็น infinity ให้ข้ามรอบนี้
   • dp[i][j] += val, อัปเดต ret = max(ret, dp[i][j])
5. คืนค่า ret

ตัวอย่างโค้ด C++

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

อินพุต

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

เอาต์พุต

3