幻想正方形

题目描述

一日，小A走在路上时看到路边摆着一面大镜子。 他对着这面镜子注视了半天，突然发现自己穿越到了另一个世界!这个世界很奇怪：他所在的地方可视为一个n行m列的矩阵，每一个位置上都有一一个非负整数或者-1。这时，他的耳边响起了一一个很空灵的声音：”如果您想要回到原来的世界， 你需要解决下面的问题：你需要在整个矩阵上选择一 一个正方形区域，使得该区域不包含任何负数，并且该区域内的数字之和最大。“然而这个问题对于小A来说还是太难了，所以他请了你来帮忙解决这个问题。

输入描述

第一行一个正整数T,表示一共有T组数据。
对于每组数据，第一行两个正整数n,m,含义见题面;
接下来一一个n行m列的整数矩阵j.
1 ≤ n,m ≤ 500,1 ≤ T ≤ 5.aij∈(-1,[0,100])

输出描述

对于每组数据，输出一行个正整数，表示满足条件的最大值。如果该矩阵全为-1,则输出0.

样例输入

1
4 4
12 0 0 6
0 0 -1 4
-1 8 1 1
4 -1 5 -1

样例输出

12

解法

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(
                new FileInputStream("data.txt")
        ));

        int T = Integer.parseInt(br.readLine().trim());
        while (T-- != 0) {
            String[] inputs = br.readLine().trim().split(" ");
            int n = Integer.parseInt(inputs[0]);
            int m = Integer.parseInt(inputs[1]);
            int[][] nums = new int[n][m];

            for (int i = 0; i < n; i++) {
                inputs = br.readLine().trim().split(" ");
                for (int j = 0; j < m; j++) {
                    nums[i][j] = Integer.parseInt(inputs[j]);
                }
            }

            System.out.println(process(n, m, nums));
        }
    }

    private static int process(int n, int m, int[][] nums) {
        if (n == 0 || m == 0) return 0;
        int res = 0;
        int[][] dp = new int[n + 1][m + 1];
        int[][] sums = new int[n+1][m+1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sums[i][j] = nums[i-1][j-1] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1];
                if (nums[i - 1][j - 1] != -1) {
                    // 最短的边
                    int minEdge = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j - 1], dp[i - 1][j])) ;
                    dp[i][j] = 1 + minEdge; // 加上自己本身
                    int len = dp[i][j];

                    int top = i - len;
                    int left = j - len;

                    int sum = sums[i][j] - sums[i][left] - sums[top][j] + sums[left][top];
                    res = Math.max(res, sum);
                }
            }
        }
        return res;
    }
}