#P18156. Painting Fences

Painting Fences

Painting Fences

一个n×m的矩形栅栏被划分成方格,每格初始为白色或黑色。请通过以下操作,把整个栅栏涂成黑色:

  • 选择一条沿格子边界、与矩形相交的水平或竖直直线。
  • 选择这条直线的一侧保持原样。
  • 先把另一侧的所有格子涂白,再把其中满足以下条件的格子涂黑:关于所选直线对称的格子为黑色。

也就是把保留一侧的图案镜像复制到另一侧;若某格的对称位置在矩形外,它不会因此变黑。

求将全部格子变黑所需的最少操作次数。保证初始至少有一个黑格。

输入格式

第一行两个正整数n、m,1≤n·m≤1000000。

接下来n行,每行一个长度为m的01串。0表示白色,1表示黑色。

输出格式

输出一个整数,表示最少操作次数。

样例

输入:

4 4
1001
0100
0110
0110

输出:

3

一种3次操作的方法:先沿第2、3行之间的线保留下方并向上镜像,得到每行都是0110;再沿第1、2列之间的线保留右侧并向左镜像,得到每行1110;最后沿第3、4列之间的线保留左侧并向右镜像,全部变黑。