标签： 矩阵

1391.检查网格中是否存在有效路径

目标

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：

  • 1 表示连接左单元格和右单元格的街道。
  • 2 表示连接上单元格和下单元格的街道。
  • 3 表示连接左单元格和下单元格的街道。
  • 4 表示连接右单元格和下单元格的街道。
  • 5 表示连接左单元格和上单元格的街道。
  • 6 表示连接右单元格和上单元格的街道。

你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。

注意：你 不能 变更街道。

如果网格中存在有效的路径，则返回 true，否则返回 false 。

示例 1：

输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。

示例 2：

输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。

示例 3：

输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。

示例 4：

输入：grid = [[1,1,1,1,1,1,3]]
输出：true

示例 5：

输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • 1 <= grid[i][j] <= 6

思路

有一个二维矩阵 grid，每个单元格的值都代表一种街道类型，判断能否从左上角出发沿着街道走到右下角。

根据当前的街道类型，初始化可走的方向，同时判断下一个位置是否超出了边界，是否访问过，是否与当前街道连通。

代码


/**
 * @date 2026-04-27 9:08
 */
public class HasValidPath1391 {

    public boolean hasValidPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, new int[]{1, 2, 3, 4, 5, 6}, visited, grid);
    }

    public static int[][][] directions = new int[][][]{
            {{0, 0}, {0, 0}},
            {{0, -1}, {0, 1}},
            {{-1, 0}, {1, 0}},
            {{0, -1}, {1, 0}},
            {{0, 1}, {1, 0}},
            {{0, -1}, {-1, 0}},
            {{0, 1}, {-1, 0}},
    };

    public static int[][][] allowedTypes = new int[][][]{
            {{}},
            {{1, 4, 6}, {1, 3, 5}},
            {{2, 3, 4}, {2, 5, 6}},
            {{1, 4, 6}, {2, 5, 6}},
            {{1, 3, 5}, {2, 5, 6}},
            {{1, 4, 6}, {2, 3, 4}},
            {{1, 3, 5}, {2, 3, 4}},
    };

    public boolean dfs(int row, int col, int[] types, boolean[][] visited, int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (row == m || row < 0 || col == n || col < 0 || visited[row][col]) {
            return false;
        }
        visited[row][col] = true;
        int type = grid[row][col];
        boolean valid = false;
        for (int t : types) {
            if (t == type) {
                valid = true;
                break;
            }
        }
        if (!valid) {
            return false;
        }
        boolean res = row == m - 1 && col == n - 1;
        for (int i = 0; i < directions[type].length; i++) {
            res = res || dfs(row + directions[type][i][0], col + directions[type][i][1], allowedTypes[type][i], visited, grid);
        }
        return res;
    }

}

性能

1559.二维网格图中探测环

目标

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。

一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。

同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。

如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。

示例 1：

输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：

示例 2：

输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：

示例 3：

输入：grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
输出：false

说明：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m <= 500
  • 1 <= n <= 500
  • grid 只包含小写英文字母。

思路

判断网格图中是否存在相同元素值形成的环，要求环的长度大于等于 4。沿着环移动总是能回到起点（沿着环顺时针或者逆时针移动，不能往回走，环中的元素只能访问一次）。

从每个格子出发 dfs，记录已访问的坐标 visited[i][j]，假设上一个访问的坐标 (px, py)，针对每一个格子枚举上下左右四个方向，下一个格子坐标为 (nx, ny)，如果不是 (px, py)，并且没越界且元素值相等，返回 visited[nx][ny] || dfs(nx, ny, x, y, visited, grid)。对于网格图，如果 (nx, ny) 不等于 (px, py) 并且已访问过说明存在环，并且环的长度至少是 4。

代码


/**
 * @date 2026-04-26 23:14
 */
public class ContainsCycle1559 {

    public static int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public boolean containsCycle(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j]) {
                    continue;
                }
                if (dfs(i, j, -1, -1, visited, grid)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int px, int py, boolean[][] visited, char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        visited[x][y] = true;
        for (int[] d : directions) {
            int nx = x + d[0];
            int ny = y + d[1];
            if ((nx != px || ny != py) && nx >= 0 && nx < m && ny >= 0 && ny < n && grid[x][y] == grid[nx][ny] &&
                    (
                            visited[nx][ny] || dfs(nx, ny, x, y, visited, grid)
                    )
            ) {
                return true;
            }
        }
        return false;
    }
}

性能

3418.机器人可以获得的最大金币数

目标

给你一个 m x n 的网格。一个机器人从网格的左上角 (0, 0) 出发，目标是到达网格的右下角 (m - 1, n - 1)。在任意时刻，机器人只能向右或向下移动。

网格中的每个单元格包含一个值 coins[i][j]：

  • 如果 coins[i][j] >= 0，机器人可以获得该单元格的金币。
  • 如果 coins[i][j] < 0，机器人会遇到一个强盗，强盗会抢走该单元格数值的 绝对值 的金币。

机器人有一项特殊能力，可以在行程中 最多感化 2个单元格的强盗，从而防止这些单元格的金币被抢走。

注意：机器人的总金币数可以是负数。

返回机器人在路径上可以获得的 最大金币数 。

示例 1：

输入： coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
输出： 8
解释：
一个获得最多金币的最优路径如下：
从 (0, 0) 出发，初始金币为 0（总金币 = 0）。
移动到 (0, 1)，获得 1 枚金币（总金币 = 0 + 1 = 1）。
移动到 (1, 1)，遇到强盗抢走 2 枚金币。机器人在此处使用一次感化能力，避免被抢（总金币 = 1）。
移动到 (1, 2)，获得 3 枚金币（总金币 = 1 + 3 = 4）。
移动到 (2, 2)，获得 4 枚金币（总金币 = 4 + 4 = 8）。

示例 2：

输入： coins = [[10,10,10],[10,10,10]]
输出： 40
解释：
一个获得最多金币的最优路径如下：
从 (0, 0) 出发，初始金币为 10（总金币 = 10）。
移动到 (0, 1)，获得 10 枚金币（总金币 = 10 + 10 = 20）。
移动到 (0, 2)，再获得 10 枚金币（总金币 = 20 + 10 = 30）。
移动到 (1, 2)，获得 10 枚金币（总金币 = 30 + 10 = 40）。

说明：

  • m == coins.length
  • n == coins[i].length
  • 1 <= m, n <= 500
  • -1000 <= coins[i][j] <= 1000

思路

有一个 m x n 的网格图，一个机器人从左上角 (0, 0) 向右或者向下移动直到 (m - 1, n - 1)。在此过程中可以收集对应格子上的金币，如果金币大于等于 0，则收集对应数量的金币，否则失去对应数量的金币。机器人有两次机会避免失去金币（感化），求可以获得的最大金币数量。

定义 dp[i][j][k] 表示到达 (i, j) 最多感化 k 次收集到的最大金币数，状态转移方程为：

  • dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) + coins[i][j]，不感化从上方与左方转移而来，加上当前格子金币
  • dp[i][j][1] = Math.max(Math.max(dp[i - 1][j][0], dp[i][j - 1][0]), Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) + coins[i][j])，感化，不计入当前格子金币，感化次数加一，不感化，计入当前格子金币，感化次数不变
  • dp[i][j][2] = Math.max(Math.max(dp[i - 1][j][1], dp[i][j - 1][1]), Math.max(dp[i - 1][j][2], dp[i][j - 1][2]) + coins[i][j])，同上

代码


/**
 * @date 2026-04-02 8:44
 */
public class MaximumAmount3418 {

    public int maximumAmount(int[][] coins) {
        int m = coins.length;
        int n = coins[0].length;
        int[][][] dp = new int[m][n][3];
        dp[0][0][0] = coins[0][0];
        dp[0][0][1] = Math.max(0, coins[0][0]);
        dp[0][0][2] = Math.max(0, dp[0][0][1]);
        for (int j = 1; j < n; j++) {
            dp[0][j][0] = dp[0][j - 1][0] + coins[0][j];
            dp[0][j][1] = Math.max(dp[0][j - 1][0], dp[0][j - 1][1] + coins[0][j]);
            dp[0][j][2] = Math.max(dp[0][j - 1][1], dp[0][j - 1][2] + coins[0][j]);
        }
        for (int i = 1; i < m; i++) {
            dp[i][0][0] = dp[i - 1][0][0] + coins[i][0];
            dp[i][0][1] = Math.max(dp[i - 1][0][0], dp[i - 1][0][1] + coins[i][0]);
            dp[i][0][2] = Math.max(dp[i - 1][0][1], dp[i - 1][0][2] + coins[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][0], dp[i][j - 1][0]) + coins[i][j];
                dp[i][j][1] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]);
                dp[i][j][1] = Math.max(dp[i][j][1], Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) + coins[i][j]);
                dp[i][j][2] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]);
                dp[i][j][2] = Math.max(dp[i][j][2], Math.max(dp[i - 1][j][2], dp[i][j - 1][2]) + coins[i][j]);
            }
        }
        return dp[m - 1][n - 1][2];
    }

}

性能

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);
    }

}

性能

1886.判断矩阵经轮转后是否一致

目标

给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。

示例 1：

输入：mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
输出：true
解释：顺时针轮转 90 度一次可以使 mat 和 target 一致。

示例 2：

输入：mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
输出：false
解释：无法通过轮转矩阵中的元素使 equal 与 target 一致。

示例 3：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
输出：true
解释：顺时针轮转 90 度两次可以使 mat 和 target 一致。

说明：

  • n == mat.length == target.length
  • n == mat[i].length == target[i].length
  • 1 <= n <= 10
  • mat[i][j] 和 target[i][j] 不是 0 就是 1

思路

两个 n x n 矩阵 mat 与 target，判断能否通过若干次顺时针旋转 90° 使得 mat 与 target 相等。

参考 48.旋转图像 直接原地旋转 mat 比较两个矩阵是否相等，最多旋转 4 次。

代码


/**
 * @date 2026-04-16 17:10
 */
public class FindRotation1886 {

    public boolean findRotation(int[][] mat, int[][] target) {
        int n = mat.length;
        here:
        for (int i = 0; i < 4; i++) {
            rotate(mat);
            for (int a = 0; a < n; a++) {
                for (int b = 0; b < n; b++) {
                    if (mat[a][b] != target[a][b]) {
                        continue here;
                    }
                }
            }
            return true;
        }
        return false;
    }

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

}

性能

3643.垂直翻转子矩阵

目标

给你一个 m x n 的整数矩阵 grid，以及三个整数 x、y 和 k。

整数 x 和 y 表示一个 正方形子矩阵 的左上角下标，整数 k 表示该正方形子矩阵的边长。

你的任务是垂直翻转子矩阵的行顺序。

返回更新后的矩阵。

示例 1：

输入： grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], x = 1, y = 0, k = 3
输出： [[1,2,3,4],[13,14,15,8],[9,10,11,12],[5,6,7,16]]
解释：
上图展示了矩阵在变换前后的样子。

示例 2：

输入： grid = [[3,4,2,3],[2,3,4,2]], x = 0, y = 2, k = 2
输出： [[3,4,4,2],[2,3,2,3]]
解释：
上图展示了矩阵在变换前后的样子。

说明：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 100
  • 0 <= x < m
  • 0 <= y < n
  • 1 <= k <= min(m - x, n - y)

思路

将矩阵 grid 的正方形子矩阵 (x, y, k) 上下翻转，(x, y) 表示子矩阵的左上顶点，k为子矩阵边长。

根据题意交换正方形子矩阵的上下对称的行即可。

代码


/**
 * @date 2026-04-17 11:11
 */
public class ReverseSubmatrix3643 {

    public int[][] reverseSubmatrix(int[][] grid, int x, int y, int k) {
        int l = k / 2;
        for (int i = 0; i < l; i++) {
            for (int j = y; j < y + k; j++) {
                int tmp = grid[x + i][j];
                grid[x + i][j] = grid[x + k - i - 1][j];
                grid[x + k - i - 1][j] = tmp;
            }
        }
        return grid;
    }
}

性能