← 返回题目列表

AtCoder · oidashi_b

B. 熄灯

中文机器翻译题面 查看原题

問題文

有一天,太郎在散步时,一架奇怪的机器从天而降。太郎对这台机器很好奇,决定把它捡起来检查一下。

显然这台机器有一个垂直的H方形,水平W有一些呈正方形排列的灯,可以有两种状态:开和关,当你按下某个灯时,该灯和与该灯相邻的上、下、左、右的灯的开/关状态似乎颠倒了。

如果按下中心的红色圆圈灯

不过,部分灯因坠落冲击而破碎,无法再推。然而,按下相邻的灯似乎可以将损坏的灯的状态恢复正常。

太郎关心的是他需要按下灯才能关闭所有灯的最少次数。求出太郎君需要按灯的最少次数来关闭所有灯。


入力

输入是按以下格式从标准输入给出的。 (标准输入中的变量已更正。(18:38))

H W
s_{0,0} s_{0,1} ... s_{0,(W-1)}
s_{1,0} s_{1,1} ... s_{1,(W-1)}
.
.
.
s_{(H-1),0} s_{(H-1),1} ... s_{(H-1),(W-1)}
N
x_1 y_1
x_2 y_2
.
.
.
x_n y_n
  • 第一行,H, W (5 \leq H,W, H \times W \leq 400) 表示机器上灯的行数和列数。
  • 从第二行开始H行应以空格分隔。W的0或 您将获得一个号码1。0是当灯状态为OFF时,1表示灯状态为ON。
  • H+1坏灯数量上线 给出了N(0 \leq N \leq W \times H)。 (16:21 补充)
  • H+2一行又一行N行显示一列损坏的灯。 给出x_i(0 \leq x_i \leq W-1), 行y_i (0 \leq y_i \leq H-1)。
  • 这个问题保证有一个程序可以关闭所有的灯。 (16:15 补充)
  • 相同的坐标不能给出两次。换句话说,i \neq j 如果 x_i \neq x_j 或 y_i \neq y_j 成立。 (18:08 添加)

出力

设置关闭所有灯的最小翻转次数。 请输出1行。在输出末尾添加换行符。


入力例1

5 5
0 0 0 0 0
1 1 0 0 1
0 1 1 1 1
1 0 1 0 1
1 0 0 0 0
0

出力例1

5

入力例2

5 5
0 0 0 0 0
1 1 0 0 1
0 1 1 1 1
1 0 1 0 1
1 0 0 0 0
1
1 2

出力例2

9