[Login|Register]
Problems

Status

Rank

Problem 1240
黑屋
Time Limit: 3000ms
Memory Limit: 65536kb
Description
哈里波特来到了一个魔法房间,黑魔法师派了影子怪物在此房间等着哈里波特,影子怪物只能生活在没有灯光照射的区域,房间的屋顶有n*m个小灯,每个小灯能够照到地上固定的范围,且所有灯照的范围没有重叠部分,有些灯亮着,有些灯灭着,灭着的灯下面就会出现阴影,影子怪物就会攻击哈利波特,现在哈利波特找到了你,给你房间的灯的状态,哈利波特可以远程遥控灯的开关,灯的状态改变为:如果一个灯的状态改变了,那么他前后左右四个灯的状态全都改变。你的任务是计算出最少要改变多少次灯的状态,才能把所有灯都点亮。
Input
有多组输入数据。每组第一行两个整数,n(1<=n<=100)和m(1<=m<=15),接下来n行,每行m个数据,0代表灯关着,1代表灯开着。
Output
对于每组输入数据输出一个整数表示能把所有灯都点亮的最少的改变灯的状态数,如果无法点亮所有灯,输出"no solution".
Sample Input
3 3
1 0 1
0 0 0
1 0 1
2 5
0 0 0 0 0 
0 0 0 0 0
Sample Output
1
3
Source
多校联合HRBEU
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.4ms with 1 query(s).