問題一覧 > 通常問題

No.3430 Flip the Grid

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 46
作問者 : まみめ / テスター : harel syndrome hirayuu_yc rogi52 👑 qand kidodesu 👑 ArcAki Eku
お気に入りにしたユーザー ProblemId : 12871 / 自分の提出
問題文最終更新日: 2026-01-12 11:32:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest YNUCPC Contest 2 (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns, and each cell has $A_{i,j}$ written on it. $A_{i,j}$ is either $0$ or $1$.
Consider the following operation.

  • Choose a $2\times2$ subgrid and flip the $01$ values of its $4$ cells.
    Formally, choose integers $i,j \ (1 \leq i \leq H-1, 1 \leq j \leq W-1)$, and for each of $A_{i,j},A_{i,j+1},A_{i+1,j},A_{i+1,j+1}$, replace it with $1$ if it is $0$, and with $0$ if it is $1$.

Find the minimum possible sum of all numbers written on the grid after performing this operation $0$ or more times.

Input

  • $2 \leq H,W\leq 2000$
  • $A_{i,j} \in \lbrace0, 1\rbrace$
  • All input values are integers.

The input is given from Standard Input in the following format.

$H$ $W$  
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$  
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$  
$\vdots$   
$A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$  

Output

Find the minimum possible sum of all numbers written on the grid after performing the operation $0$ or more times.
Print a newline at the end.

Sample

Sample 1
Input
2 3
0 1 1
1 1 1
Output
1

By flipping the $4$ cells $A_{12}, A_{13}, A_{22}, A_{23}$, the sum of the numbers on the grid becomes $1$.
The sum cannot be made any smaller.

Sample 2
Input
3 3
1 1 1
1 1 1
1 1 1
Output
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。