#LQB0053. 轴对称图形

轴对称图形

提示信息:

轴对称图形:定义为平面内,一个图形沿一条直线折叠,直线两旁的部分能够完全重合的图形。这条直线为该图形的对称轴。
例如,下图中为常见的轴对称图形,图中的红色虚线为对应图形的一条对称轴。

编程实现:

在一张 n 行 m 列的白色方格纸内,有一些单元格为黑色,恰巧这些黑色的单元格连成了一个图形,即每个黑色单元格至少有一个与之相邻(上下左右)的黑色单元格。啾啾想再填充一些单元格为黑色,使得所有黑色单元格连成的图形有一条竖直的对称轴。请计算啾啾最少还需填充多少个单元格,如果图形已经有一条竖直的对称轴,则输出 0。
例如,n = 5,m = 5;5 行 5 列方格纸中,黑色单元格如下:

啾啾将单元格填充为以下图形,就可以使所有黑色单元格连成的图形有一条竖直的对称轴(红色虚线表示此对称轴):

所以啾啾最少还需填充 2 个单元格。

输入格式

第一行输入两个整数 n,mn,m(以一个空格隔开),分别表示方格纸的行数和列数。
接下来输入 nn 行,每行输入 mm 个整数(整数为 1100),11 表示该单元格为黑色,00 表示该单元格为白色,每行整数之间以一个空格隔开。
数据保证至少有 22 个单元格为黑色。

输出格式

输出一个整数,表示啾啾最少还需填充的单元格数量;如果图形已经有一条竖直的对称轴,则输出 00

样例输入输出

样例输入1

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

样例输出1

2

数据范围与测试点说明

  • 3n1003\le n\le 100
  • 3m1003\le m\le 100
  • 输入仅包含 0011,且至少有 2211
  • 初始黑色单元格连通:每个黑色单元格至少与一个上下左右相邻的黑色单元格相邻。

时间限制与内存限制

  • 时间限制:11
  • 内存限制:10241024 KiB