問題文
有一天,太郎在散步时,一架奇怪的机器从天而降。太郎对这台机器很好奇,决定把它捡起来检查一下。
显然这台机器有一个垂直的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