O fazendeiro Jack é muito pobre. Ele quer iluminar toda a fazenda, mas com o mínimo de custo. Uma lâmpada pode iluminar sua própria célula e seus oito vizinhos. Ele organizou as lâmpadas em seu campo, mas ele precisa de sua ajuda para descobrir se ele manteve ou não outras lâmpadas.

Lâmpadas extras: as lâmpadas que, ao serem removidas da fazenda, não farão diferença no número de células acesas. Além disso, as lâmpadas que você apontará não serão removidas uma a uma, mas serão removidas simultaneamente.

Nota: A única ação que você pode executar é remover algumas lâmpadas. Você não pode reorganizar nem inserir lâmpadas. Seu objetivo final é remover o número máximo de lâmpadas, de modo que todas as células que foram acesas antes ainda estejam acesas.

Ajude o fazendeiro Jack a detectar o número máximo de lâmpadas inúteis para que ele possa usá-las em outros lugares.

Entrada

Você será indicado nas dimensões da primeira linha do campo M e N. As próximas linhas M seguem contendo N caracteres, cada um representando o campo.

'1' representa a célula onde a lâmpada é mantida.

'0' representa uma célula vazia.

Resultado

Você precisa emitir um número inteiro contendo o número de lâmpadas inúteis.

Entrada de amostra:

3 3
100
010
001

Saída de amostra:

2

Vencedora:

Como é código de golfe, o vencedor será aquele que concluirá a tarefa com sucesso em menos número de caracteres

Mathematica 186 (ganancioso) e 224 (todas as combinações)

Solução gananciosa

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]

Isso apaga as luzes supérfluas uma a uma. Se a cobertura da luz não diminui quando a luz se apaga, essa luz pode ser eliminada. A abordagem gananciosa é muito rápida e pode lidar facilmente com matrizes de 15x15 e muito maiores (veja abaixo). Ele retorna soluções únicas, mas não se sabe se isso é ideal ou não. Ambas as abordagens, nas versões golfadas, retornam o número de luzes não utilizadas. As abordagens sem golfe também exibem as grades, como abaixo.

Antes:

Depois de:

Soluções ideais usando todas as combinações de luzes (224 caracteres)

Com agradecimentos a @ Clément.

Versão ungolfed usando todas as combinações de luzes

fA função de transformação morfológica usada em sameCoverageQtrata como iluminado (valor = 1 em vez de zero) o quadrado 3 x3 no qual cada luz reside.Quando uma luz está próxima à borda da fazenda, apenas os quadrados (menos de 9) dentro das bordas da a fazenda é contada. Não há contagem excessiva; um quadrado aceso por mais de uma lâmpada é simplesmente aceso. O programa apaga cada luz e verifica se a cobertura geral de iluminação da fazenda é reduzida.Se não estiver, essa luz será eliminada.

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]conta o número de células sinalizadas. É usado para contar as luzes e também para contar as células acesas

sameCoverageQ[mat1, mat2] testa se as células acesas em mat1 são iguais ao número de células acesas em mat2.MorphologicalTransform [[mat] pega uma matriz de luzes e retorna uma matriz` das células que acendem.

c[m1]pega todas as combinações de luzes de m1 e as testa quanto à cobertura. Entre os que têm cobertura máxima, seleciona aqueles que têm menos lâmpadas. Cada um deles é uma solução ideal.

Exemplo 1:

Uma configuração 6x6

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

Todas as soluções ideais.

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

Versão Golfed usando todas as combinações de luzes.

Esta versão calcula o número de luzes não utilizadas. Não exibe as grades.

c retorna o número de luzes não 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]conta o número de células sinalizadas. É usado para contar as luzes e também para contar as células acesas

s[mat1, mat2] testa se as células acesas em mat1 são iguais ao número de células acesas em mat2.t [[mat] pega uma matriz de luzes e retorna uma matriz` das células que acendem.

c[j]pega todas as combinações de luzes de j e testa sua cobertura. Entre os que têm cobertura máxima, seleciona aqueles que têm menos lâmpadas. Cada um deles é uma solução ideal.

Exemplo 2

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

Duas luzes podem ser salvas com a mesma cobertura de iluminação. 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 usando máscaras de bits. Lé uma lista das luzes, em que cada luz é representada por um número inteiro com (até) 9 bits definidos para seu padrão de luz. Em seguida, pesquisamos exaustivamente subconjuntos dessa lista cujo bit a bit - ou é o mesmo que o bit a bit - ou da lista inteira. O subconjunto mais curto é o vencedor.

m é uma máscara que impede a envolvência dos bits ao mudar.

Java 6 - 509 bytes

Fiz algumas suposições sobre os limites e resolvi o problema conforme declarado neste 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);}}

Execute assim: 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;}

Ruby, 303

[isto foi codificado para responder a uma versão anterior da pergunta; leia a nota abaixo]

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

Convertendo em matrizes de booleanos e comparando vizinhanças para alterações.

Limitação (?): O tamanho máximo do campo do farm é 1.000 x 1.000. O problema declara "O fazendeiro Jack é muito pobre", então estou assumindo que a fazenda dele não é maior. ;-) A limitação pode ser removida adicionando 2 caracteres.

NOTA: Desde que comecei a codificar isso, parece que os requisitos da pergunta foram alterados. O esclarecimento a seguir foi adicionado "as lâmpadas que você apontará não serão removidas uma a uma, mas serão removidas simultaneamente" . A ambiguidade da pergunta original me permitiu salvar algum código testando as remoções de lâmpadas individuais . Portanto, minha solução não funcionará para muitos casos de teste sob os novos requisitos. Se eu tiver tempo, vou consertar isso. Eu não posso. Por favor, não marque esta resposta, pois outras respostas aqui podem ser totalmente compatíveis.

APL, 97 caracteres / bytes *

Assume um ambiente ⎕IO←1e ⎕ML←3APL.

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

Versão não destruída:

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

Concordo que mais casos de teste seriam melhores. Aqui está um aleatório:

Entrada:

5 5
10001
01100
00001
11001
00010

Saída (lâmpadas inúteis):

5

Layout com lâmpadas mínimas (não incluídas na versão golfed):

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 pode ser escrito na sua própria (legado) de conjunto de caracteres de byte único que mapeia símbolos APL para os 128 valores de bytes superiores. Portanto, para fins de pontuação, um programa de N caracteres que usa apenas caracteres ASCII e símbolos APL pode ser considerado como N bytes.}

C ++ 5.806 bytes

Ainda não está otimizado para tamanho. Mas como existem poucos concorrentes, deixarei por enquanto.

Cabeçalho do campo:

#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);
};

}

CPP de campo:

#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);
}

}

E um conjunto de testes para mostrar que o código faz o que foi criado para fazer:

#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

Não é uma solução de golfe, mas achei este problema interessante:

#!/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'
      );
   }
}

(A E / S foi retirada para que eu pudesse mostrar testes concretos)

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()