首页 > 试题广场 >

牛牛的灯光调整

[编程题]牛牛的灯光调整
  • 热度指数:76 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛有一个n行m列的矩阵,每个格子里有一盏灯,灯有亮(1)和灭(0)两种状态。每次操作,牛牛可以选择一个格子,将其状态取反,同时,与这个格子相邻的上下左右四个格子(如果存在)的灯的状态也会被取反。请问牛牛至少需要进行多少次操作,才能使所有的灯都亮起来?

输入描述:
输入第一行包含两个整数n,m,分别表示矩阵的行数和列数。(1<=n<=100,1<=m<=15)。接下来的n行,每行包含m个由空格分隔的整数,表示初始的矩阵状态,其中0表示灯是灭的,1表示灯是亮的。


输出描述:
输出一个整数,表示至少需要进行的操作次数。如果无法使所有的灯都亮起来,就输出"no solution"。
示例1

输入

3 3
0 1 1
0 0 1
0 1 1

输出

1