#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列之间的线保留左侧并向右镜像,全部变黑。