079 - Two by Two（★3）
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 3 点
問題文
H \times W の 2 次元配列 A が与えられます。あなたは以下の 2 種類の操作を好きな順番で何度でも行うことが出来ます。
- 整数 x, y (1 \leq x \lt H, 1 \leq y \lt W) を選び、A_{x, y}, A_{x+1, y}, A_{x, y+1}, A_{x+1, y+1} の値をそれぞれ 1 ずつ増やす。
- 整数 x, y (1 \leq x \lt H, 1 \leq y \lt W) を選び、A_{x, y}, A_{x+1, y}, A_{x, y+1}, A_{x+1, y+1} の値をそれぞれ 1 ずつ減らす。
操作を 0 回以上行うことで A を B に一致させることは可能でしょうか。 もし可能ならば、最小の操作回数も答えてください。
制約
- 2 \leq H, W \leq 100
- 0 \leq A_{i, j}, B_{i, j} \leq 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
B_{1, 1} B_{1, 2} \cdots B_{1, W}
B_{2, 1} B_{2, 2} \cdots B_{2, W}
\vdots
B_{H, 1} B_{H, 2} \cdots B_{H, W}
出力
操作を行うことで A を B に一致させることが可能である場合は 1 行目に Yes、2 行目に最小の操作回数を出力してください。
A を B に一致させることが不可能である場合は No と出力してください。
入力例 1
3 3 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0
出力例 1
Yes 1
(x, y)=(1, 1) を選んで 1 増やす操作を行うことで A が B に一致します。
入力例 2
3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
出力例 2
No
どのように操作を行っても A を B に一致させることは出来ません。
入力例 3
5 5 6 17 18 29 22 39 50 25 39 25 34 34 8 25 17 28 48 25 47 42 27 47 24 32 28 4 6 3 29 28 48 50 21 48 29 44 44 19 47 28 4 49 46 29 28 4 49 45 1 1
出力例 3
Yes 140