月度归档： 2026 年 3 月

3474.字典序最小的生成字符串

目标

给你两个字符串，str1 和 str2，其长度分别为 n 和 m 。

如果一个长度为 n + m - 1 的字符串 word 的每个下标 0 <= i <= n - 1 都满足以下条件，则称其由 str1 和 str2 生成：

  • 如果 str1[i] == 'T'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 相等，即 word[i..(i + m - 1)] == str2。
  • 如果 str1[i] == 'F'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 不相等，即 word[i..(i + m - 1)] != str2。

返回可以由 str1 和 str2 生成 的 字典序最小 的字符串。如果不存在满足条件的字符串，返回空字符串 ""。

如果字符串 a 在第一个不同字符的位置上比字符串 b 的对应字符在字母表中更靠前，则称字符串 a 的 字典序 小于 字符串 b。

如果前 min(a.length, b.length) 个字符都相同，则较短的字符串字典序更小。

子字符串 是字符串中的一个连续、非空 的字符序列。

示例 1：

输入: str1 = "TFTF", str2 = "ab"
输出: "ababa"
解释:
下表展示了字符串 "ababa" 的生成过程：
下标  T/F   长度为 m 的子字符串
0    'T'        "ab"
1    'F'        "ba"
2    'T'        "ab"
3    'F'        "ba"
字符串 "ababa" 和 "ababb" 都可以由 str1 和 str2 生成。
返回 "ababa"，因为它的字典序更小。

示例 2：

输入: str1 = "TFTF", str2 = "abc"
输出: ""
解释:
无法生成满足条件的字符串。

示例 3：

输入: str1 = "F", str2 = "d"
输出: "a"

说明:

  • 1 <= n == str1.length <= 10^4
  • 1 <= m == str2.length <= 500
  • str1 仅由 'T' 或 'F' 组成。
  • str2 仅由小写英文字母组成。

思路

有两个字符串 str1 和 str2，长度分别为 n 和 m。对于长度为 n + m - 1 的字符串 word，如果对于每一个位置 i 都满足以下条件，则称其由 str1 和 str2 生成：

  • 如果 str1[i] == T，那么从 i 开始长度为 m 的子串 word[i ~ i + m - 1] 与 str2 相同。
  • 如果 str1[i] == F，那么从 i 开始长度为 m 的子串 word[i ~ i + m - 1] 与 str2 不同。

返回由 str1 和 str2 生成的字典序最小的字符串，如果无法生成返回空字符。

// todo

代码

性能

2840.判断通过操作能否让字符串相等II

目标

给你两个字符串 s1 和 s2 ，两个字符串长度都为 n ，且只包含 小写 英文字母。

你可以对两个字符串中的 任意一个 执行以下操作 任意 次：

选择两个下标 i 和 j ，满足 i < j 且 j - i 是 偶数，然后 交换 这个字符串中两个下标对应的字符。

如果你可以让字符串 s1 和 s2 相等，那么返回 true ，否则返回 false 。

示例 1：

输入：s1 = "abcdba", s2 = "cabdab"
输出：true
解释：我们可以对 s1 执行以下操作：
- 选择下标 i = 0 ，j = 2 ，得到字符串 s1 = "cbadba" 。
- 选择下标 i = 2 ，j = 4 ，得到字符串 s1 = "cbbdaa" 。
- 选择下标 i = 1 ，j = 5 ，得到字符串 s1 = "cabdab" = s2 。

示例 2：

输入：s1 = "abe", s2 = "bea"
输出：false
解释：无法让两个字符串相等。

说明：

  • n == s1.length == s2.length
  • 1 <= n <= 10^5
  • s1 和 s2 只包含小写英文字母。

思路

有两个长度为 n 的字符串 s1 和 s2，判断能否通过操作使二者相等，每次操作交换下标之差为偶数的字母。

与 2839.判断通过操作能否让字符串相等I 相比，字符串长度由 4 变成了 n，操作的下标之差由 2 变成了偶数。

由于本身使用的就是一般解法，没有去特判具体的下标，可以复用之前的代码。

将字母根据下标分组，

代码


/**
 * @date 2026-03-30 15:41
 */
public class CheckStrings2840 {

    public boolean checkStrings(String s1, String s2) {
        int[][] chars = new int[2][26];
        int n = s1.length();
        for (int i = 0; i < n; i++) {
            chars[i % 2][s1.charAt(i) - 'a']++;
            chars[i % 2][s2.charAt(i) - 'a']--;
        }
        for (int[] ca : chars) {
            for (int c : ca) {
                if (c != 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

性能

2839.判断通过操作能否让字符串相等I

目标

给你两个字符串 s1 和 s2 ，两个字符串的长度都为 4 ，且只包含 小写 英文字母。

你可以对两个字符串中的 任意一个 执行以下操作 任意 次：

  • 选择两个下标 i 和 j 且满足 j - i = 2 ，然后 交换 这个字符串中两个下标对应的字符。

如果你可以让字符串 s1 和 s2 相等，那么返回 true ，否则返回 false 。

示例 1：

输入：s1 = "abcd", s2 = "cdab"
输出：true
解释： 我们可以对 s1 执行以下操作：
- 选择下标 i = 0 ，j = 2 ，得到字符串 s1 = "cbad" 。
- 选择下标 i = 1 ，j = 3 ，得到字符串 s1 = "cdab" = s2 。

示例 2：

输入：s1 = "abcd", s2 = "dacb"
输出：false
解释：无法让两个字符串相等。

说明：

  • s1.length == s2.length == 4
  • s1 和 s2 只包含小写英文字母。

思路

有两个长度为 4 的字符串 s1 和 s2，判断能否通过操作使二者相等，每次操作可将第一个与第三个 或者 第二个与第四个 字母交换。

实际上就是判断 s1[0]s1[2] 与 s2[0]s2[2] 或者 s2[2]s2[0] ，以及 s1[1]s1[3] 与 s2[1]s2[3] 或者 s2[3]s2[1] 是否相等。

为了避免复杂判断，直接根据奇偶性分组，s1 中的字母 +1，s2 中的字母 -1，最后判断字母出现次数是否为 0 即可。

代码


/**
 * @date 2026-03-29 16:28
 */
public class CanBeEqual2839 {

    public boolean canBeEqual(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        Map<Character, Integer>[] map = new HashMap[2];
        Arrays.setAll(map, x -> new HashMap<>());
        for (int i = 0; i < 4; i++) {
            int rem = i % 2;
            map[rem].merge(chars1[i], 1, Integer::sum);
            map[rem].merge(chars2[i], -1, Integer::sum);
        }
        for (int i = 0; i < 2; i++) {
            for (Integer value : map[i].values()) {
                if (value != 0) {
                    return false;
                }
            }
        }
        return true;
    }

}

性能

2573.找出对应LCP矩阵的字符串

目标

对任一由 n 个小写英文字母组成的字符串 word ，我们可以定义一个 n x n 的矩阵，并满足：

  • lcp[i][j] 等于子字符串 word[i,...,n-1] 和 word[j,...,n-1] 之间的最长公共前缀的长度。

给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字典序最小的字符串 word 。如果不存在这样的字符串，则返回空字符串。

对于长度相同的两个字符串 a 和 b ，如果在 a 和 b 不同的第一个位置，字符串 a 的字母在字母表中出现的顺序先于 b 中的对应字母，则认为字符串 a 按字典序比字符串 b 小。例如，"aabd" 在字典上小于 "aaca" ，因为二者不同的第一位置是第三个字母，而 'b' 先于 'c' 出现。

示例 1：

输入：lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
输出："abab"
解释：lcp 对应由两个交替字母组成的任意 4 字母字符串，字典序最小的是 "abab" 。

示例 2：

输入：lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
输出："aaaa"
解释：lcp 对应只有一个不同字母的任意 4 字母字符串，字典序最小的是 "aaaa" 。

示例 3：

输入：lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
输出：""
解释：lcp[3][3] 无法等于 3 ，因为 word[3,...,3] 仅由单个字母组成；因此，不存在答案。

说明：

  • 1 <= n == lcp.length == lcp[i].length <= 1000
  • 0 <= lcp[i][j] <= n

思路

代码

性能

2946.循环移位后的矩阵相似检查

目标

给你一个下标从 0 开始且大小为 m x n 的整数矩阵 mat 和一个整数 k 。请你将矩阵中的 奇数 行循环 右 移 k 次，偶数 行循环 左 移 k 次。

如果初始矩阵和最终矩阵完全相同，则返回 true ，否则返回 false 。

示例 1：

输入：mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2
输出：true
解释：
初始矩阵如图一所示。
图二表示对奇数行右移一次且对偶数行左移一次后的矩阵状态。
图三是经过两次循环移位后的最终矩阵状态，与初始矩阵相同。
因此，返回 true 。

示例 2：

输入：mat = [[2,2],[2,2]], k = 3
输出：true
解释：由于矩阵中的所有值都相等，即使进行循环移位，矩阵仍然保持不变。因此，返回 true 。

示例 3：

输入：mat = [[1,2]], k = 1
输出：false
解释：循环移位一次后，mat = [[2,1]]，与初始矩阵不相等。因此，返回 false 。

说明：

  • 1 <= mat.length <= 25
  • 1 <= mat[i].length <= 25
  • 1 <= mat[i][j] <= 25
  • 1 <= k <= 50

思路

有一个 m x n 矩阵 mat，将奇数行（行标 1 开始）右移 k，偶数行左移 k，判断最终矩阵与初始矩阵是否相同。

依题意模拟即可，右移后的下标 (i + k) % n，左移后的下标 (i - k + n) % n。

实际上无需判断奇偶行，row[i] 左移 k 之后是否等于 row[i]，等价于 row[i] 右移 k 之后是否等于 row[i]。

代码


/**
 * @date 2026-03-27 8:56
 */
public class AreSimilar2946 {

    public boolean areSimilar(int[][] mat, int k) {
        int n = mat[0].length;
        for (int[] row : mat) {
            for (int j = 0; j < n; j++) {
                if (row[j] != row[(j + k) % n]) {
                    return false;
                }
            }
        }
        return true;
    }

}

性能

3548.等和矩阵分割II

目标

给你一个由正整数组成的 m x n 矩阵 grid。你的任务是判断是否可以通过 一条水平或一条垂直分割线 将矩阵分割成两部分，使得：

  • 分割后形成的每个部分都是 非空 的。
  • 两个部分中所有元素的和 相等 ，或者总共 最多移除一个单元格 （从其中一个部分中）的情况下可以使它们相等。
  • 如果移除某个单元格，剩余部分必须保持 连通 。

如果存在这样的分割，返回 true；否则，返回 false。

注意： 如果一个部分中的每个单元格都可以通过向上、向下、向左或向右移动到达同一部分中的其他单元格，则认为这一部分是 连通 的。

示例 1：

输入： grid = [[1,4],[2,3]]
输出： true
解释：
在第 0 行和第 1 行之间进行水平分割，结果两部分的元素和为 1 + 4 = 5 和 2 + 3 = 5，相等。因此答案是 true。

示例 2：

输入： grid = [[1,2],[3,4]]
输出： true
解释：
在第 0 列和第 1 列之间进行垂直分割，结果两部分的元素和为 1 + 3 = 4 和 2 + 4 = 6。
通过从右侧部分移除 2 （6 - 2 = 4），两部分的元素和相等，并且两部分保持连通。因此答案是 true。

示例 3：

输入： grid = [[1,2,4],[2,3,5]]
输出： false
解释：
在第 0 行和第 1 行之间进行水平分割，结果两部分的元素和为 1 + 2 + 4 = 7 和 2 + 3 + 5 = 10。
通过从底部部分移除 3 （10 - 3 = 7），两部分的元素和相等，但底部部分不再连通（分裂为 [2] 和 [5]）。因此答案是 false。

示例 4：

输入： grid = [[4,1,8],[3,2,6]]
输出： false
解释：
不存在有效的分割，因此答案是 false。

说明：

  • 1 <= m == grid.length <= 10^5
  • 1 <= n == grid[i].length <= 10^5
  • 2 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^5

思路

有一个 m x n 矩阵，判断能否用一条水平线或者垂线将矩阵分割成非空的两部分使得它们的元素和相等。允许进行至多一次操作，选择任一部分删除一个单元格，要求删除后这部分仍保持连通。

与 3546.等和矩阵分割I 相比，本题允许进行一次操作，在保证连通性的前提下删掉一个单元格。

先考虑水平分割，垂直分割只需将矩阵旋转 90° 即可。计算所有元素和 totalSum，按行遍历矩阵，累加当前元素和 curSum，如果要删掉已访问过的某一元素 x，需要满足 curSum - x == totalSum - curSum，当然也可能是删掉另一部分，只需将矩阵上下翻转即可。

删除单元格要保证连通性，如果矩阵只有 1 列，那么只能删除最上面的或者切线上面一个单元格。如果水平切完上面部分只有一行，那么只能删除第一个或者最后一个单元格。其余情况可以任意删除单元格。使用哈希集合记录访问过的元素值，除了上面的特殊情况，只要 x 在哈希集合中就说明是合法分割。

这个题目的思想就是抽象、变形、统一处理逻辑。

代码


/**
 * @date 2026-03-26 10:28
 */
public class CanPartitionGrid3548 {

    public boolean canPartitionGrid(int[][] grid) {
        long totalSum = 0L;
        for (int[] row : grid) {
            for (int num : row) {
                totalSum += num;
            }
        }
        return cut(grid, totalSum) || cut(rotate(grid), totalSum);
    }

    public boolean cut(int[][] grid, long totalSum) {
        if (check(grid, totalSum)) {
            return true;
        }
        return check(flip(grid), totalSum);
    }

    public boolean check(int[][] grid, long totalSum) {
        int m = grid.length;
        int n = grid[0].length;
        Set<Long> set = new HashSet<>();
        set.add(0L);
        long prefix = 0L;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                set.add((long) grid[i][j]);
                prefix += grid[i][j];
            }
            long x = prefix * 2 - totalSum;
            if (i == 0) {
                if (x == grid[0][0] || x == grid[0][n - 1] || x == 0) {
                    return true;
                }
            } else if (n == 1) {
                if (x == grid[0][0] || x == grid[i][0] || x == 0) {
                    return true;
                }
            } else if (set.contains(x)) {
                return true;
            }
        }
        return false;
    }

    public int[][] rotate(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] res = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[j][i] = grid[i][j];
            }
        }
        return res;
    }

    public int[][] flip(int[][] grid) {
        int m = grid.length;
        for (int i = 0; i < m / 2; i++) {
            int[] tmp = grid[m - i - 1];
            grid[m - i - 1] = grid[i];
            grid[i] = tmp;
        }
        return grid;
    }

}

性能

3546.等和矩阵分割I

目标

给你一个由正整数组成的 m x n 矩阵 grid。你的任务是判断是否可以通过 一条水平或一条垂直分割线 将矩阵分割成两部分，使得：

  • 分割后形成的每个部分都是 非空 的。
  • 两个部分中所有元素的和 相等 。

如果存在这样的分割，返回 true；否则，返回 false。

示例 1：

输入： grid = [[1,4],[2,3]]
输出： true
解释：
在第 0 行和第 1 行之间进行水平分割，得到两个非空部分，每部分的元素之和为 5。因此，答案是 true。

示例 2：

输入： grid = [[1,3],[2,4]]
输出： false
解释：
无论是水平分割还是垂直分割，都无法使两个非空部分的元素之和相等。因此，答案是 false。

说明：

  • 1 <= m == grid.length <= 10^5
  • 1 <= n == grid[i].length <= 10^5
  • 2 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^5

思路

有一个 m x n 矩阵，判断能否用一条水平线或者垂直线将矩阵分割成两部分，使得两部分的和相等，并且每一部分非空。

先求出总和，根据题意枚举所有分割水平线与垂直线判断两部分的和是否相等。

代码


/**
 * @date 2026-03-25 9:03
 */
public class CanPartitionGrid3546 {

    public boolean canPartitionGrid(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        long sum = 0L;
        for (int[] row : grid) {
            for (int num : row) {
                sum += num;
            }
        }
        if (sum % 2 == 1) {
            return false;
        }
        long half = sum / 2;
        long prefix = 0L;
        for (int i = 0; i < m - 1; i++) {
            for (int num : grid[i]) {
                prefix += num;
            }
            if (prefix << 1 == sum) {
                return true;
            } else if (prefix > half) {
                break;
            }
        }
        prefix = 0L;
        for (int j = 0; j < n - 1; j++) {
            for (int i = 0; i < m; i++) {
                prefix += grid[i][j];
            }
            if (prefix << 1 == sum) {
                return true;
            } else if (prefix > half) {
                break;
            }
        }
        return false;
    }

}

性能

2906.构造乘积矩阵

目标

给你一个下标从 0 开始、大小为 n m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

  • 对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

返回 grid 的乘积矩阵。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。

示例 2：

输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。

说明：

  • 1 <= n == grid.length <= 10^5
  • 1 <= m == grid[i].length <= 10^5
  • 2 <= n * m <= 10^5
  • 1 <= grid[i][j] <= 10^9

思路

已知 n x m 矩阵 grid，构造一个乘积矩阵 p 满足 p[i][j] 的值等于除了 grid[i][j] 外所有元素的乘积对 12345 取余。

计算所有元素的乘积会溢出，而保存取模后的乘积不支持除法。

---------
----X----
---------

实际上就是要快速计算出 - 的乘积。可以使用前后缀分解计算取模后的乘积。针对每一行进行前后缀分解，前缀的的最后一列以及后缀的第一列就是整行的乘积结果，对这 n 行整行的乘积再次进行前后缀分解。这样就可以快速求出 0 ~ i - 1 行的乘积，以及 i + 1 ~ n - 1 的乘积，然后对第 i 行，使用行的前后缀分解可以快速计算 grid[i][0 ~ j - 1] 以及 grid[i][j + 1 ~ m - 1] 的乘积。

代码


/**
 * @date 2026-03-24 8:57
 */
public class ConstructProductMatrix2906 {

    public int[][] constructProductMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int mod = 12345;
        int[][] prefix = new int[m][n + 1];
        int[][] suffix = new int[m][n + 1];
        for (int i = 0; i < m; i++) {
            prefix[i][0] = 1;
            suffix[i][n] = 1;
            for (int j = 0; j < n; j++) {
                prefix[i][j + 1] = (int) ((long) prefix[i][j] * grid[i][j] % mod);
                suffix[i][n - j - 1] = (int) ((long) suffix[i][n - j] * grid[i][n - j - 1] % mod);
            }
        }
        int[] rowPrefix = new int[m + 1];
        int[] rowSuffix = new int[m + 1];
        rowPrefix[0] = 1;
        rowSuffix[m] = 1;
        for (int i = 0; i < m; i++) {
            rowPrefix[i + 1] = (int) ((long) rowPrefix[i] * prefix[i][n] % mod);
            rowSuffix[m - i - 1] = (int) ((long) rowSuffix[m - i] * suffix[m - i - 1][0] % mod);
        }
        int[][] p = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                p[i][j] = (int) (((long) rowPrefix[i] * rowSuffix[i + 1] % mod) * ((long) prefix[i][j] * suffix[i][j + 1] % mod) % mod);
            }
        }
        return p;
    }

}

性能

1594.矩阵的最大非负积

目标

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 10^9 + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。

注意，取余是在得到最大积之后执行的。

示例 1：

输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。

示例 2：

输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
输出：8
解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)

示例 3：

输入：grid = [[1,3],[0,-4]]
输出：0
解释：最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)

说明：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 15
  • -4 <= grid[i][j] <= 4

思路

有一个矩阵 grid，从左上角 (0, 0) 出发向右或向下移动到达 (m - 1, n - 1)。路径的乘积指路径经过的所有元素乘积，返回最大的非负乘积。

由于存在负值，总的最大非负路径可能由最小值与当前值相乘得到。

定义 dp[i][j][0] 表示到达 (i, j) 的最大路径积，dp[i][j][1] 表示到达 (i, j) 的最小路径积。状态转移方程为：

  • dp[i][j][0] = Math.max(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]) 最小值与当前值相乘
  • dp[i][j][0] = Math.max(dp[i][j][0], Math.max(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j])) 最大值与当前值相乘
  • dp[i][j][1] = Math.min(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]) 最小值与当前值相乘
  • dp[i][j][1] = Math.min(dp[i][j][1], Math.min(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j])) 最大值与当前值相乘

代码


/**
 * @date 2026-03-23 9:12
 */
public class MaxProductPath1594 {

    public int maxProductPath(int[][] grid) {
        int mod = 1000000007;
        int m = grid.length;
        int n = grid[0].length;
        long[][][] dp = new long[m][n][2];
        dp[0][0][0] = grid[0][0];
        dp[0][0][1] = grid[0][0];
        for (int j = 1; j < n; j++) {
            dp[0][j][0] = dp[0][j - 1][0] * grid[0][j];
            dp[0][j][1] = dp[0][j - 1][1] * grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            dp[i][0][0] = dp[i - 1][0][0] * grid[i][0];
            dp[i][0][1] = dp[i - 1][0][1] * grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
                dp[i][j][0] = Math.max(dp[i][j][0], Math.max(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j]));
                dp[i][j][1] = Math.min(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
                dp[i][j][1] = Math.min(dp[i][j][1], Math.min(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j]));
            }
        }
        return dp[m - 1][n - 1][0] < 0 ? -1 : (int) (dp[m - 1][n - 1][0] % mod);
    }

}

性能