时间轴

2026-03-25

init

题目：

P3546 等和矩阵分割 I

https://leetcode.cn/problems/equal-sum-grid-partition-i/description/?envType=daily-question&envId=2026-03-25

前缀和换皮题目，注意相加时可能超过int表示的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <vector>
using std::vector;

class Solution {
    public:
        bool canPartitionGrid(vector<vector<int> > &grid)
        {
                // 1 <= m == grid.length <= 105
                // 1 <= n == grid[i].length <= 105
                // 2 <= m * n <= 105
                // 1 <= grid[i][j] <= 105
                int i, j, m = grid.size(), n = grid[0].size();
                int total = m * n;
                long last;
                vector<long> prefix_sum(total, 0);
                vector<long> suffix_sum(total, 0);

                // 水平分割
                last = grid[0][0];
                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                if (i == 0 && j == 0)
                                        continue;
                                prefix_sum[i * n + j] = last + prefix_sum[i * n + j - 1];
                                last = grid[i][j];
                        }
                }

                last = grid[m - 1][n - 1];
                for (i = m - 1; i >= 0; i--) {
                        for (j = n - 1; j >= 0; j--) {
                                if (i == m - 1 && j == n - 1)
                                        continue;
                                suffix_sum[i * n + j] = last + suffix_sum[i * n + j + 1];
                                last = grid[i][j];
                        }
                }

                for (i = 0; i < m - 1; i++) {
                        if (prefix_sum[i * n + n - 1] + grid[i][n - 1] == suffix_sum[i * n + n - 1])
                                return true;
                }

                // 垂直分割
                prefix_sum[0] = 0;
                last = grid[0][0];
                for (j = 0; j < n; j++) {
                        for (i = 0; i < m; i++) {
                                if (i == 0 && j == 0)
                                        continue;
                                prefix_sum[j * m + i] = last + prefix_sum[j * m + i - 1];
                                last = grid[i][j];
                        }
                }

                suffix_sum[total - 1] = 0;
                last = grid[m - 1][n - 1];
                for (j = n - 1; j >= 0; j--) {
                        for (i = m - 1; i >= 0; i--) {
                                if (i == m - 1 && j == n - 1)
                                        continue;
                                suffix_sum[j * m + i] = last + suffix_sum[j * m + i + 1];
                                last = grid[i][j];
                        }
                }
                for (j = 1; j < n; j++) {
                        if (prefix_sum[j * m] == suffix_sum[j * m] + grid[0][j])
                                return true;
                }

                return false;
        }
};