10
Farmer Jack is very poor. He wants to light his whole farm but with minimum of cost. A lamp can illuminate its own cell as well as its eight neighbors . He has arranged the lamps in his field but he needs your help in finding out whether or not he has kept any extra lamps.
Extra lamps : Lamps which on removing from the farm will make no difference to the number of cells lit. Also, the lamps you will point will not be removed one by one, but they will be removed simultaneously.
Note: The only action you can perform is to remove some lamps. You can neither rearrange nor insert lamps. Your final target is to remove maximum number of lamps such that every cell which was lit before is still lit.
Help Farmer Jack in spotting the maximum number of useless lamps so that he can use them elsewhere.
Input
You will be given in the first line dimensions of the field M and N.Next M lines follow containing N characters each representing the field.
'1' represents cell where lamp is kept.
'0' represents an empty cell.
Output
You have to output an integer containing number of useless lamps.
Sample Input:
3 3
100
010
001
Sample Output:
2
Winner:
Since it is code golf, winner will be the one who will successfully complete the task in least number of characters
@PeterTaylor I have edited my post. Do you still have a confusion? – user2369284 – 2014-01-01T19:24:51.777
Much better. Thanks. – Peter Taylor – 2014-01-01T19:33:23.213
may we assume the input ends with a newline? – John Dvorak – 2014-01-01T19:51:59.983
Yes sure, you can do that – user2369284 – 2014-01-01T19:53:29.437
1This looks like homework. – Johannes – 2014-01-01T23:34:24.923
Can you post a couple more complex examples? Is there a limit for the number of lamps? – aditsu quit because SE is EVIL – 2014-01-01T23:39:35.317
Given the complexity of the problem, and the number of variables and parameters that need naming, I recommend that it be a code-challenge. Also, you really ought to require that the program show which lights are useless (by their position or by showing which ones are indispensable).Finally, you ought to include more complex examples that we are expected to provide solutions to. Otherwise, it will be very difficult to know for sure whether procedures do what they were intended to do. – DavidC – 2014-01-02T02:21:30.993
On the other hand, there may be a much simpler way to identify useless lamps... – DavidC – 2014-01-02T02:41:54.243
1Are we guaranteed that the input lamps will light the whole farm? I'm going to guess no... – Keith Randall – 2014-01-02T05:04:21.330
@KeithRandall Your guess is right. The input lamps may or may not light the whole field – user2369284 – 2014-01-02T08:51:41.693
This is just minimum set cover with a strange encoding and a silly story. – Tim Seguine – 2014-01-02T13:24:48.723
@user2369284 if the farm is not fully lit, what should our output be? A negative integer whose absolute value is the minimum number of additional lamps needed? – Panzercrisis – 2014-01-03T05:10:33.340
@Panzercrisis I would assume the farm can be partially lit. We are still required to provide the number of lamps that can be safely removed without switching off cells that were originally lit. – Tobia – 2014-01-03T21:35:08.967