fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8. int m, n;
  9. cin >> m >> n;
  10.  
  11. vector<vector<int>> mat(m, vector<int>(n));
  12.  
  13. // Nhập ma trận
  14. for (int i = 0; i < m; ++i) {
  15. for (int j = 0; j < n; ++j) {
  16. cin >> mat[i][j];
  17. }
  18. }
  19.  
  20. vector<vector<int>> dp(m, vector<int>(n, 0));
  21. int maxSide = 0;
  22.  
  23. // Tính toán dp
  24. for (int i = 0; i < m; ++i) {
  25. for (int j = 0; j < n; ++j) {
  26. if (i == 0 || j == 0) {
  27. // Nếu là hàng đầu tiên hoặc cột đầu tiên
  28. dp[i][j] = 1;
  29. } else if (mat[i][j] == mat[i-1][j] && mat[i][j] == mat[i][j-1] && mat[i][j] == mat[i-1][j-1]) {
  30. // Nếu có thể mở rộng hình vuông
  31. dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
  32. } else {
  33. // Không thể mở rộng, hình vuông nhỏ nhất là 1
  34. dp[i][j] = 1;
  35. }
  36.  
  37. // Cập nhật kích thước cạnh lớn nhất
  38. maxSide = max(maxSide, dp[i][j]);
  39. }
  40. }
  41.  
  42. // Kết quả là diện tích hình vuông lớn nhất
  43. cout << maxSide * maxSide << endl;
  44.  
  45. return 0;
  46. }
Success #stdin #stdout 0s 5252KB
stdin
4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
stdout
4