問題一覧 > 通常問題

No.3558 Dominoes, Black and White

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : みうね / テスター : fluorine TKTYI HoyHoyCharhang jastaway soryuusi0219 yaaya butsurizuki wasab1 tatesoto KumaTachiRen
ProblemId : 13259 / KCPC新歓杯2026 (順位表) / 自分の提出
問題文最終更新日: 2026-05-25 17:14:03
KCPC新歓杯2026の他の問題:

問題文

縦 $N$ 行、横 $2N$ 列のマス目からなるグリッドがあります。
各マスは白または黒で塗られており、全体でちょうど $N^2$ 個のマスが白に、残りの $N^2$ 個のマスが黒に塗られています。

上から $i$ 行目 ($1 \leq i \leq N$)、左から $j$ 列目 ($1 \leq j \leq 2N$) のマスの色は文字 $S_{i,j}$ で表されます。$S_{i,j}$ が . のときは白を、# のときは黒を意味します。

あなたは、以下の操作を $0$ 回以上の任意の回数行うことができます。

  • 辺を共有して隣り合う $2$ つのマスであって、色が異なるものを選び、それらの色を入れ替える。

あなたの目標は、グリッドの左半分（$1 \leq j \leq N$）のすべてのマスを白に、右半分（$N+1 \leq j \leq 2N$）のすべてのマスを黒にすることです。
目標を達成するために必要な操作回数の最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。 

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

  • $1 \leq N \leq 1000$
  • $N$ は整数である
  • $S_i$ は . と # からなる長さ $2N$ の文字列である
  • グリッド全体で . と # はそれぞれちょうど $N^2$ 個存在する

部分点

この問題にはサブタスクによる部分点が設定されています。

サブタスク名配点制約
部分点10 点$N \leq 3$
満点90 点追加の制約はない

出力

目標を達成するために必要な操作回数の最小値を $1$ 行に出力せよ。

サンプル

サンプル1
入力
1
#.
出力
1

$1$ 回の操作で目標を達成できます。

サンプル2
入力
2
..##
..##
出力
0

最初から目標を達成しているため、操作は不要です。

サンプル3
入力
3
.#.###
#.#...
##..#.
出力
17

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