先说说使用的算法：二维前缀和+二分+枚举

做法：

  1. 先求这个矩阵的二维前缀和
  2. 枚举这个矩阵的每个美味度点，且这个点是我们所求的正方形的右下脚末端点
  3. 由于是求正方形，且每个美味度都是正数，所以我们可以二分这个正方形的边长，边长越大，正方形美味度越大。我们只需要二分美味度总和到 就可以了。（sum是整个矩阵的美味度和）
  4. 还有需要处理的边界就是可能正方形美味度总和 的最小的正方形可能也会是答案。举个例子：边长为3的正方形的美味度总和为40，边长为4的正方形的美味度总和为55，矩阵美味度总和为100。因此边长为4的更好。而更大的边长是不可能比以4为边的正方形要更优的。

时间复杂度：

空间复杂度： 

#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    long long sum = 0;
    vector<vector<long long>> a(n + 1, vector<long long>(m + 1)), b(n + 1, vector<long long>(m + 1));
    for(int i = 1; i <= n ; i++)
        for(int j = 1; j <= m ; j++) {
            cin >> a[i][j];
            sum += a[i][j];
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
        }

    long long ans = 1e18;
    for(int i = 1; i <= n ; i++)
        for(int j = 1; j <= m ; j++) {
            int l = 1, r = min(i, j);
            int x = 0, y = 0;
            long long digit = 0;
            while(l < r) {
                int mid = (l + r + 1) >> 1;
                x = i - mid + 1;
                y = j - mid + 1;
                digit = b[i][j] - b[x - 1][j] - b[i][y - 1] + b[x - 1][y - 1];
                if (digit <= sum / 2) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }

            x = i - l + 1;
            y = j - l + 1;
            digit = b[i][j] - b[x - 1][j] - b[i][y - 1] + b[x - 1][y - 1];
            ans = min(ans, abs(digit - (sum - digit)));
            
		  	//特殊边界处理 
            x--, y--;
            if (x >= 1 && x <= n && y >= 1 && y <= m) {
                digit = b[i][j] - b[x - 1][j] - b[i][y - 1] + b[x - 1][y - 1];
                ans = min(ans, abs(digit - (sum - digit)));
            }
        }

    cout << ans;
}

int main() {
    solve();
    return 0;
}