El granjero Jack es muy pobre. Quiere iluminar toda su granja pero con un costo mínimo. Una lámpara puede iluminar su propia celda y sus ocho vecinos. Él ha dispuesto las lámparas en su campo, pero necesita su ayuda para averiguar si ha guardado o no lámparas adicionales.

Lámparas adicionales: Lámparas que al retirar de la granja no harán ninguna diferencia en el número de celdas encendidas. Además, las lámparas que apuntará no se eliminarán una por una, sino que se eliminarán simultáneamente.

Nota: La única acción que puede realizar es quitar algunas lámparas. No puede reorganizar ni insertar lámparas. Su objetivo final es eliminar el número máximo de lámparas de manera que cada celda que se encendió antes todavía esté encendida.

Ayuda al granjero Jack a detectar la cantidad máxima de lámparas inútiles para que pueda usarlas en otro lugar.

Entrada

Se le dará en las primeras dimensiones de la línea del campo de M y N .Next M líneas siguen conteniendo N caracteres cada uno que representa el campo.

'1' representa la celda donde se guarda la lámpara.

'0' representa una celda vacía.

Salida

Debe generar un número entero que contenga varias lámparas inútiles.

Entrada de muestra:

3 3
100
010
001

Salida de muestra:

2

Ganador:

Como se trata de un código de golf, el ganador será el que completará con éxito la tarea en el menor número de caracteres.

Mathematica 186 (codicioso) y 224 (todas las combinaciones)

Solución codiciosa

t=MorphologicalTransform;n@w_:=Flatten@w~Count~1
p_~w~q_:=n[p~t~Max]==n[q~t~Max]
g@m_:=Module[{l=m~Position~1,r,d=m},While[l!={},If[w[m,r=ReplacePart[d,#-> 0]&    
[l[[1]]]],d=r];l=Rest@l];n@m-n@d]

Esto apaga las luces superfluas una por una. Si la cobertura de la luz no disminuye cuando la luz se apaga, esa luz se puede eliminar. El enfoque codicioso es muy rápido y puede manejar fácilmente matrices de 15x15 y mucho más grandes (ver más abajo). Devuelve una solución única, pero no se sabe si eso es óptimo o no. Ambos enfoques, en las versiones de golf, devuelven el número de luces no utilizadas. Los enfoques sin golf también muestran las cuadrículas, como se muestra a continuación.

Antes de:

Después:

Soluciones óptimas que utilizan todas las combinaciones de luces (224 caracteres)

Gracias a @ Clément.

Versión sin golf con todas las combinaciones de luces.

La función de transformación morfológica utilizada en los sameCoverageQtratamientos como iluminado (valor = 1 en lugar de cero) del cuadrado de 3 x3 en el que reside cada luz. Cuando una luz está cerca del borde de la granja, solo los cuadrados (menos de 9) dentro de los bordes de se cuenta la granja. No se cuenta demasiado; simplemente se enciende un cuadrado iluminado por más de una lámpara. El programa apaga cada luz y comprueba si se reduce la cobertura de iluminación general en la granja. Si no es así, esa luz se elimina.

nOnes[w_]:=Count[Flatten@w,1]
sameCoverageQ[m1_,m2_]:=nOnes[MorphologicalTransform[m1,Max]]==
  nOnes[MorphologicalTransform[m2,Max]]

(*draws a grid with light bulbs *)
h[m_]:=Grid[m/.{1-> Style[\[LightBulb],24],0-> ""},Frame-> All,ItemSize->{1,1.5}]

c[m1_]:=GatherBy[Cases[{nOnes[MorphologicalTransform[ReplacePart[Array[0&,Dimensions[m1]],
#/.{{j_Integer,k_}:> {j,k}-> 1}],Max]],#,Length@#}&/@(Rest@Subsets[Position[m1,1]]),
{nOnes[MorphologicalTransform[m1,Max]],_,_}],Last][[1,All,2]]

nOnes[matrix]cuenta el número de celdas marcadas. Se usa para contar las luces y también para contar las celdas encendidas

sameCoverageQ[mat1, mat2] prueba si las celdas encendidas en mat1 son iguales al número de celdas encendidas en mat2.MorphologicalTransform [[mat] toma una matriz de luces y devuelve una matriz` de las celdas que encienden.

c[m1]toma todas las combinaciones de luces de m1 y las prueba para su cobertura. Entre los que tienen la máxima cobertura, selecciona los que tienen menos bombillas. Cada uno de estos es una solución óptima.

Ejemplo 1:

Una configuración de 6x6

(*all the lights *)
m=Array[RandomInteger[4]&,{6,6}]/.{2-> 0,3->0,4->0}
h[m]

Todas las soluciones óptimas.

(*subsets of lights that provide full coverage *)
h/@(ReplacePart[Array[0&,Dimensions[m]],#/.{{j_Integer,k_}:> {j,k}-> 1}]&/@(c[m]))

Versión de golf con todas las combinaciones de luces.

Esta versión calcula el número de luces no utilizadas. No muestra las cuadrículas.

c Devuelve el número de luces no utilizadas.

n@w_:=Flatten@w~Count~1;t=MorphologicalTransform;
c@r_:=n@m-GatherBy[Cases[{n@t[ReplacePart[Array[0 &,Dimensions[r]],#
/.{{j_Integer,k_}:> {j,k}-> 1}],Max],#,Length@#}&/@(Rest@Subsets[r~Position~1]),
{n[r~t~Max],_,_}],Last][[1,1,3]]

n[matrix]cuenta el número de celdas marcadas. Se usa para contar las luces y también para contar las celdas encendidas

s[mat1, mat2] prueba si las celdas encendidas en mat1 son iguales al número de celdas encendidas en mat2.t [[mat] toma una matriz de luces y devuelve una matriz` de las celdas que encienden.

c[j]toma todas las combinaciones de luces de j y las prueba para su cobertura. Entre los que tienen la máxima cobertura, selecciona los que tienen menos bombillas. Cada uno de estos es una solución óptima.

Ejemplo 2

m=Array[RandomInteger[4]&,{6,6}]/.{2-> 0,3->0,4->0};
m//Grid

Se pueden guardar dos luces con la misma cobertura de iluminación. cm]

2

Python, 309 caracteres

import sys
I=sys.stdin.readlines()[1:]
X=len(I[0])
L=[]
m=p=1
for c in''.join(I):m|=('\n'!=c)*p;L+=('1'==c)*[p<<X+1|p<<X|p<<X-1|p*2|p|p/2|p>>X-1|p>>X|p>>X+1];p*=2
O=lambda a:m&reduce(lambda x,y:x|y,a,0)
print len(L)-min(bin(i).count('1')for i in range(1<<len(L))if O(L)==O(x for j,x in enumerate(L)if i>>j&1))

Funciona con máscaras de bits. Les una lista de las luces, donde cada luz está representada por un número entero con (hasta) 9 bits establecidos para su patrón de luz. Luego buscamos exhaustivamente los subconjuntos de esta lista cuyo bit a bit, o es el mismo que el bit a bit, o de toda la lista. El subconjunto más corto es el ganador.

m es una máscara que evita que los bits se envuelvan al desplazarse.

Java 6 - 509 bytes

Hice algunas suposiciones sobre los límites y resolví el problema como se indicó en este momento.

import java.util.*;enum F{X;{Scanner s=new Scanner(System.in);int m=s.nextInt(),n=s.nextInt(),i=m,j,k=0,l=0,r=0,o,c,x[]=new int[30],y[]=x.clone();int[][]a=new
int[99][99],b;while(i-->0){String t=s.next();for(j=n;j-->0;)if(t.charAt(j)>48){x[l]=i;y[l++]=j;}}for(;k<l;++k)for(i=9;i-->0;)a[x[k]+i/3][y[k]+i%3]=1;for(k=1<<l;k-->0;){b=new
int[99][99];for(j=c=l;j-->0;)if((k&1<<j)>0)for(c--,i=9;i-->0;)b[x[j]+i/3][y[j]+i%3]=1;for(o=i=0;i++<m;)for(j=0;j++<n;)o|=a[i][j]^b[i][j];r=c-o*c>r?c:r;}System.out.println(r);}}

Corre así: java F <inputfile 2>/dev/null

c ++ - 477 bytes

#include <iostream>
using namespace std;int main(){
int c,i,j,m,n,p,q=0;cin>>m>>n;
int f[m*n],g[m*n],h[9]={0,-1,1,-m-1,-m,-m+1,m-1,m,m+1};
for(i=0;i<m*n;i++){f[i]=0;g[i]=0;do{c=getchar();f[i]=c-48;}while(c!='0'&&c!='1');}
for(i=0;i<m*n;i++)if(f[i])for(j=0;j<9;j++)if(i+h[j]>=0&&i+h[j]<m*n)g[i+h[j]]++;
for(i=0;i<m*n;i++)if(f[i]){p=0;for(j=0;j<9;j++)if(i+h[j]>=0&&i+h[j]<m*n)if(g[i+h[j]]<2)p++;if(p==0){for(j=0;j<9;j++)if(i+h[j]>=0&&i+h[j]<m*n)g[i+h[j]]--;q++;}}cout<<q<<endl;}

Rubí, 303

[esto fue codificado para responder una versión previa de la pregunta; lea la nota a continuación]

def b(f,m,n,r)b=[!1]*1e6;(n..n+m*n+m).each{|i|b[i-n-2,3]=b[i-1,3]=b[i+n,3]=[1]*3if f[i]};b[r*n+r+n+1,n];end
m,n=gets.split.map(&:to_i)
f=[!1]*n
m.times{(?0+gets).chars{|c|f<<(c==?1)if c>?*}}
f+=[!u=0]*n*n
f.size.times{|i|g=f.dup;g[i]?(g[i]=!1;u+=1if m.times{|r|break !1if b(f,m,n,r)!=b(g,m,n,r)}):0}
p u

Convirtiendo en matrices de booleanos y luego comparando barrios para los cambios.

Limitación (?): El tamaño máximo del campo de la granja es 1,000 x 1,000. El problema dice "El granjero Jack es muy pobre", así que supongo que su granja no es más grande. ;-) La limitación se puede eliminar agregando 2 caracteres.

NOTA: Desde que comencé a codificar esto, parece que los requisitos de la pregunta cambiaron. Se agregó la siguiente aclaración "las lámparas que señalará no se eliminarán una por una, sino que se eliminarán simultáneamente" . La ambigüedad de la pregunta original me permitió guardar algo de código al probar la eliminación de lámparas individuales . Por lo tanto, mi solución no funcionará para muchos casos de prueba bajo los nuevos requisitos. Si tengo tiempo, arreglaré esto. Yo quiza no. Por favor, no vote esta respuesta, ya que otras respuestas aquí pueden ser totalmente compatibles.

APL, 97 caracteres / bytes *

Asume una ⎕IO←1y ⎕ML←3entorno de APL.

m←{s↑⊃∨/,v∘.⊖(v←⍳3)⌽¨⊂0⍪0⍪0,0,s⍴⍵}⋄n-⌊/+/¨t/⍨(⊂m f)≡¨m¨(⊂,f)\¨t←⊂[1](n⍴2)⊤⍳2*n←+/,f←⍎¨⊃{⍞}¨⍳↑s←⍎⍞

Versión sin golf:

s ← ⍎⍞                                         ⍝ read shape of field
f ← ⍎¨ ⊃ {⍞}¨ ⍳↑s                              ⍝ read original field (lamp layout)
n ← +/,f                                       ⍝ original number of lamps
c ← ⊂[1] (n⍴2) ⊤ ⍳2*n                          ⍝ all possible shutdown combinations
m ← {s↑ ⊃ ∨/ ,v ∘.⊖ (v←⍳3) ⌽¨ ⊂ 0⍪0⍪0,0, s⍴⍵}  ⍝ get lighted cells given a ravelled field
l ← m¨ (⊂,f) \¨ c                              ⍝ map of lighted cells for every combination
k ← c /⍨ (⊂ m f) ≡¨ l                          ⍝ list of successful combinations
u ← ⌊/ +/¨ k                                   ⍝ min lamps used by a successful comb.
⎕ ← n-u                                        ⍝ output number of useless lamps

⎕ ← s⍴ ⊃ (⊂,f) \¨ (u= +/¨ k) / k               ⍝ additional: print the layout with min lamps

Estoy de acuerdo en que más casos de prueba serían mejores. Aquí hay uno al azar:

Entrada:

5 5
10001
01100
00001
11001
00010

Salida (lámparas inútiles):

5

Diseño con lámparas mínimas (no incluidas en la versión de golf):

0 0 0 0 1
0 1 0 0 0
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ^{*: APL se puede escribir en su propio} juego de
^{caracteres de un solo byte (heredado) que asigna símbolos APL a los valores superiores de 128 bytes. Por lo tanto, para fines de puntuación, un programa de N caracteres que solo usa caracteres ASCII y símbolos APL puede considerarse que tiene una longitud de N bytes.}

C ++ 5.806 bytes

Esto aún no está optimizado para el tamaño. Pero como hay pocos concursantes, lo dejaré así por ahora.

FarmersField Header:

#pragma once

namespace FarmersLand
{

class FarmersField
{
private:
    unsigned _m_size, _n_size;
    int * _lamp, * _lumination;
    char * _buffer;
    void _illuminate(unsigned m, unsigned n);
    void _deluminate(unsigned m, unsigned n);
    void _removeLamp(unsigned m, unsigned n);
    void _setLamp(unsigned m, unsigned n);
    int _canRemoveLamp(unsigned m, unsigned n);
    int _coordsAreValid(unsigned m, unsigned n);
    int _getLuminationLevel(unsigned m, unsigned n);
    int * _allocIntArray(unsigned m, unsigned n);
    int _coordHelper(unsigned m, unsigned n);
public:
    FarmersField(char * input[]);
    FarmersField(const FarmersField & field);
    ~FarmersField(void);
    int RemoveLamps(void);
    char * Cstr(void);
};

}

FarmersField CPP:

#include "FarmersField.h"
#include <stdio.h>


namespace FarmersLand
{

void FarmersField::_illuminate(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        ++this -> _lumination[this -> _coordHelper(m,n)];
    }
}

void FarmersField::_deluminate(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        --this -> _lumination[this -> _coordHelper(m,n)];
    }
}

void FarmersField::_removeLamp(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        unsigned mi_start = (m == 0) ? 0 : m - 1;
        unsigned mi_end = m + 1;
        unsigned ni_start = (n == 0) ? 0 : n - 1;
        unsigned ni_end = n + 1;

        for(unsigned mi = mi_start; mi <= mi_end; ++mi)
        {
            for(unsigned ni = ni_start; ni <= ni_end; ++ni)
            {
                this -> _deluminate(mi, ni);
            }
        }
        --this -> _lamp[this -> _coordHelper(m,n)];
    }
}

void FarmersField::_setLamp(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        unsigned mi_start = (m == 0) ? 0 : m - 1;
        unsigned mi_end = m + 1;
        unsigned ni_start = (n == 0) ? 0 : n - 1;
        unsigned ni_end = n + 1;

        for(unsigned mi = mi_start; mi <= mi_end; ++mi)
        {
            for(unsigned ni = ni_start; ni <= ni_end; ++ni)
            {
                this -> _illuminate(mi, ni);
            }
        }
        ++this -> _lamp[this -> _coordHelper(m,n)];
    }
}

int FarmersField::_canRemoveLamp(unsigned m, unsigned n)
{
    unsigned can = 1;
    unsigned mi_start = (m == 0) ? 0 : m - 1;
    unsigned mi_end =   (m == (this->_m_size - 1)) ? m : m + 1;
    unsigned ni_start = (n == 0) ? 0 : n - 1;
    unsigned ni_end =   (n == (this->_n_size - 1)) ? n : n + 1;

    for(unsigned mi = mi_start; mi <= mi_end; ++mi)
    {
        for(unsigned ni = ni_start; ni <= ni_end; ++ni)
        {
            if( 1 >= this -> _getLuminationLevel(mi, ni) )
            {
                can = 0;
            }
        }
    }
    return can;
}

int FarmersField::_coordsAreValid(unsigned m, unsigned n)
{
    return m < this -> _m_size && n < this -> _n_size;
}

int FarmersField::_getLuminationLevel(unsigned m, unsigned n)
{
    if(this -> _coordsAreValid(m,n))
    {
        return this -> _lumination[this -> _coordHelper(m,n)];
    }
    else
    {
        return 0;
    }
}

int * FarmersField::_allocIntArray(unsigned m, unsigned n)
{
    int * a = new int[m * n];
    for(unsigned i = 0; i < m*n; ++i)
    {
        a[i] = 0;
    }
    return a;
}

int FarmersField::_coordHelper(unsigned m, unsigned n)
{
    return m * this -> _n_size + n;
}

int FarmersField::RemoveLamps(void)
{
    int r = 0;
    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            if(this -> _canRemoveLamp(m,n))
            {
                ++r;
                this -> _removeLamp(m,n);
            }
        }
    }
    return r;
}

char * FarmersField::Cstr(void)
{
    unsigned size = this -> _m_size * this -> _n_size + _m_size ;
    unsigned target = 0;
    delete(this -> _buffer);
    this -> _buffer = new char[ size ];
    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            this -> _buffer[target++] =  (0 == this -> _lamp[this -> _coordHelper(m,n)])? '0' : '1';
        }
        this -> _buffer[target++] = '-'; 
    }
    this -> _buffer[size - 1 ] = 0;
    return this -> _buffer;
}

FarmersField::FarmersField(char * input[])
{
    sscanf_s(input[0], "%u %u", &this -> _m_size, &this -> _n_size);

    this -> _lamp = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _lumination = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _buffer = new char[1];

    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            if('0' != input[m+1][n])
            {
                this -> _setLamp(m,n);
            }
        }
    }
}

FarmersField::FarmersField(const FarmersField & field)
{
    this -> _m_size = field._m_size;
    this -> _n_size = field._n_size;

    this -> _lamp = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _lumination = this -> _allocIntArray(this -> _m_size, this -> _n_size);
    this -> _buffer = new char[1];

    for(unsigned m = 0 ; m < this -> _m_size; ++m)
    {
        for(unsigned n = 0 ; n < this -> _n_size; ++n)
        {
            if(0 != field._lamp[this -> _coordHelper(m,n)])
            {
                this -> _setLamp(m,n);
            }
        }
    }

}

FarmersField::~FarmersField(void)
{
    delete(this -> _lamp);
    delete(this -> _lumination);
    delete(this -> _buffer);
}

}

Y un conjunto de pruebas para mostrar que el código hace para lo que fue creado:

#include "../../Utility/GTest/gtest.h"

#include "FarmersField.h"

TEST(FarmersField, Example1) 
{
    using namespace FarmersLand;
    char * input[] = {"3 3", "100", "010", "001"};
    FarmersField f(input);
    EXPECT_STREQ("100-010-001", f.Cstr());
    EXPECT_EQ(2, f.RemoveLamps());
    EXPECT_STREQ("000-010-000", f.Cstr());
}

TEST(FarmersField, Example2) 
{
    using namespace FarmersLand;
    char * input[] = {"3 6", "100000", "010000", "001000"};
    FarmersField f(input);
    EXPECT_STREQ("100000-010000-001000", f.Cstr());
    EXPECT_EQ(1, f.RemoveLamps());
    EXPECT_STREQ("000000-010000-001000", f.Cstr());
 }

TEST(FarmersField, Example3) 
{
    using namespace FarmersLand;
    char * input[] = {"6 3", "100", "010", "001", "000", "000", "000",};
    FarmersField f(input);
    EXPECT_STREQ("100-010-001-000-000-000", f.Cstr());
    EXPECT_EQ(1, f.RemoveLamps());
    EXPECT_STREQ("000-010-001-000-000-000", f.Cstr());
 }

TEST(FarmersField, Example4) 
{
    using namespace FarmersLand;
    char * input[] = {"3 3", "000", "000", "000",};
    FarmersField f(input);
    EXPECT_STREQ("000-000-000", f.Cstr());
    EXPECT_EQ(0, f.RemoveLamps());
    EXPECT_STREQ("000-000-000", f.Cstr());
 }

TEST(FarmersField, Example5) 
{
    using namespace FarmersLand;
    char * input[] = {"3 3", "111", "111", "111",};
    FarmersField f(input);
    EXPECT_STREQ("111-111-111", f.Cstr());
    EXPECT_EQ(8, f.RemoveLamps());
    EXPECT_STREQ("000-010-000", f.Cstr());
 }

TEST(FarmersField, Example6) 
{
    using namespace FarmersLand;
    char * input[] = {"6 6", "100001", "001010", "001001", "001010", "110000", "100001",};
    FarmersField f(input);
    EXPECT_STREQ("100001-001010-001001-001010-110000-100001", f.Cstr());
    EXPECT_EQ(6, f.RemoveLamps());
    EXPECT_STREQ("100011-001010-000000-000010-010000-000001", f.Cstr());
 }

Perl 3420 bytes

No es una solución de golf, pero este problema me pareció interesante:

#!/usr/bin/perl
use strict;
use warnings; 

{
   package Farm; 
   use Data::Dumper; 

   # models 8 nearest neighbors to position i,j forall i,j
   my $neighbors = [ [-1, -1],
                     [-1,  0],
                     [-1, +1], 
                     [ 0, -1], 
                     # current pos 
                     [ 0,  1], 
                     [+1, -1], 
                     [+1,  0], 
                     [+1, +1] ];

   sub new { 
      my ($class, %attrs) = @_; 
      bless \%attrs, $class;
   }  

   sub field { 
      my $self = shift;
      return $self->{field};
   }

   sub rows {
      my $self = shift;
      return $self->{rows};
   }

   sub cols {
      my $self = shift;
      return $self->{cols};
   }
   sub adjacents {
      my ($self, $i, $j) = @_;

      my @adjs; 
   NEIGHBORS:
      for my $neighbor ( @$neighbors ) {
         my ($imod, $jmod) = ($neighbor->[0] + $i, $neighbor->[1] + $j); 
         next NEIGHBORS 
            if $imod >= $self->rows || $jmod >= $self->cols;

         # push neighbors
         push @adjs, 
            $self->field->[$imod]->[$jmod];

      }

      return @adjs;
   }

   sub islit { 
      my ($lamp) = @_;

      return defined $lamp && $lamp == 1;
   }

   sub can_remove_lamp { 
      my ($self, $i, $j) = @_; 

      return scalar grep { islit($_) } $self->adjacents($i, $j);
   }

   sub remove_lamp { 
      my ($self, $i, $j) = @_;

      $self->field->[$i]->[$j] = 0;
   }

   sub remove_lamps {
      my ($self) = @_; 

      my $removed = 0;
      for my $i ( 0 .. @{ $self->field } - 1) {
         for my $j ( 0 .. @{ $self->field->[$i] } - 1 ) { 
            next unless islit( $self->field->[$i]->[$j] ); 

            if( $self->can_remove_lamp($i, $j) ) {
               $removed++; 
               $self->remove_lamp($i, $j);
            }
         }
      }

      return $removed;
   }

   1;
}

{ # Tests
   use Data::Dumper;
   use Test::Deep;
   use Test::More; 

   { # 3x3 field
      my $farm = Farm->new( rows  => 3,
                            cols  => 3,
                            field => [ [1,0,0],
                                       [0,1,0],
                                       [0,0,1]
                                     ]
      );

      is( 2, 
          $farm->remove_lamps,
          'Removed 2 overlapping correctly'
      );

      is_deeply( $farm->field, 
                 [ [0,0,0],
                   [0,0,0],
                   [0,0,1],
                 ],
                 'Field after removing lamps matches expected'
      );

   }

   { # 5x5 field
      my $farm = Farm->new( rows  => 5,
                            cols  => 5,
                            field => [ [0,0,0,0,0],
                                       [0,1,0,0,0],
                                       [0,0,1,0,0],
                                       [0,0,0,0,0],
                                       [0,0,0,0,0]
                                     ]
      );

      is( 1, 
          $farm->remove_lamps,
          'Removed 1 overlapping lamp correctly'
      );

      is_deeply( $farm->field,
                 [ [0,0,0,0,0],
                   [0,0,0,0,0],
                   [0,0,1,0,0],
                   [0,0,0,0,0],
                   [0,0,0,0,0],
                 ],
                 'Field after removing lamps matches expected'
      );
   }
}

(Se sacaron las E / S para poder mostrar pruebas concretas)

Python - 305 bytes

import sys,itertools
w,h=map(int,input().split());w+=1
l=[i for i,c in enumerate(sys.stdin.read())if c=="1"]
f=lambda l:{i+j for i in l for j in(0,1,-1,w-1,w,w+1,1-w,-w,-w-1)if(i+j+1)%w}&set(range(w*h))
for n in range(1,len(l)):
 for c in itertools.combinations(l,n):
  if f(c)^f(l):print(len(l)-n);exit()