mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-05 15:31:43 +08:00
85 lines
3.7 KiB
HTML
85 lines
3.7 KiB
HTML
<p>You are given an <code>m x n</code> matrix <code>grid</code> of positive integers. Your task is to determine if it is possible to make <strong>either one horizontal or one vertical cut</strong> on the grid such that:</p>
|
|
|
|
<ul>
|
|
<li>Each of the two resulting sections formed by the cut is <strong>non-empty</strong>.</li>
|
|
<li>The sum of elements in both sections is <b>equal</b>, or can be made equal by discounting <strong>at most</strong> one single cell in total (from either section).</li>
|
|
<li>If a cell is discounted, the rest of the section must <strong>remain connected</strong>.</li>
|
|
</ul>
|
|
|
|
<p>Return <code>true</code> if such a partition exists; otherwise, return <code>false</code>.</p>
|
|
|
|
<p><strong>Note:</strong> A section is <strong>connected</strong> if every cell in it can be reached from any other cell by moving up, down, left, or right through other cells in the section.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [[1,4],[2,3]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">true</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2025/03/30/lc.jpeg" style="height: 180px; width: 180px;" /></p>
|
|
|
|
<ul>
|
|
<li>A horizontal cut after the first row gives sums <code>1 + 4 = 5</code> and <code>2 + 3 = 5</code>, which are equal. Thus, the answer is <code>true</code>.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [[1,2],[3,4]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">true</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2025/04/01/chatgpt-image-apr-1-2025-at-05_28_12-pm.png" style="height: 180px; width: 180px;" /></p>
|
|
|
|
<ul>
|
|
<li>A vertical cut after the first column gives sums <code>1 + 3 = 4</code> and <code>2 + 4 = 6</code>.</li>
|
|
<li>By discounting 2 from the right section (<code>6 - 2 = 4</code>), both sections have equal sums and remain connected. Thus, the answer is <code>true</code>.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [[1,2,4],[2,3,5]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">false</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2025/04/01/chatgpt-image-apr-2-2025-at-02_50_29-am.png" style="height: 180px; width: 180px;" /></strong></p>
|
|
|
|
<ul>
|
|
<li>A horizontal cut after the first row gives <code>1 + 2 + 4 = 7</code> and <code>2 + 3 + 5 = 10</code>.</li>
|
|
<li>By discounting 3 from the bottom section (<code>10 - 3 = 7</code>), both sections have equal sums, but they do not remain connected as it splits the bottom section into two parts (<code>[2]</code> and <code>[5]</code>). Thus, the answer is <code>false</code>.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 4:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [[4,1,8],[3,2,6]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">false</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>No valid cut exists, so the answer is <code>false</code>.</p>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= m == grid.length <= 10<sup>5</sup></code></li>
|
|
<li><code>1 <= n == grid[i].length <= 10<sup>5</sup></code></li>
|
|
<li><code>2 <= m * n <= 10<sup>5</sup></code></li>
|
|
<li><code>1 <= grid[i][j] <= 10<sup>5</sup></code></li>
|
|
</ul>
|