O 3BV de um O tabuleiro do Campo Minado representa o número mínimo de cliques com o botão esquerdo necessários para resolver o tabuleiro se você já conhece a solução. Significa ” Valor de referência da diretoria da Bechtel “. Aqui “s seu site explicando isso.
Abaixo está um quadro do Campo Minado resolvido. As bandeiras indicam minas; os ladrilhos sem minas indicam a contagem de minas adjacentes, inclusive diagonalmente, exceto que os ladrilhos que devem ter ” 0 ” são deixados em branco. A imagem mostra quais peças precisam ser clicadas para resolver o tabuleiro.
Os cliques contados para o 3BV são:
- Um para cada área inundada de blocos em branco (zero minas adjacentes) e seus vizinhos não vazios.
- Um para cada bloco não mine.
Outro exemplo (3BV = 39)
Dada uma matriz 2D de valores, 0 para limpar e 1 para uma mina (ou um booleano), retornar o 3BV .
As dimensões de uma placa serão no mínimo 8×8 e no máximo 2 4×30, inclusive. Seu programa deve lidar com todas as placas possíveis, não apenas os exemplos.
Observação: uma placa nunca conterá apenas minas.
Exemplo de E / S:
[[0,0,0,0,0,0,0,0], [0,0,0,1,0,0,0,0], [0,0,0,1,0,0,1,0], [0,1,0,0,1,0,0,0], [0,0,1,0,0,0,0,1], [0,0,0,1,0,0,0,0], [0,0,0,0,0,0,1,0], [0,0,0,0,0,0,0,1]] 23 [[0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0], [0,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0], [0,1,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,0,1,0], [0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0], [0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,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,0,1,0,1,0,0,1,1,0,1], [0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1], [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0], [0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0], [0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0], [1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1], [0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0], [0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,1,1,0,0], [0,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0], [0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0], [0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0]] 187 Comentários
- Uma matriz de inteiros está correta como entrada? Cada número inteiro codifica uma linha.
- @KarlNapf Não. A entrada deve ser reconhecível como um quadro, conforme mostrado.
- Você poderia fornecer mais casos de teste, possivelmente incluindo a entrada com base no imagens e talvez um caso de teste de dimensões máximas?
Resposta
MATLAB, 92 90 86 83 79 74 72 bytes
x=input("");I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N Esta solução aceita a entrada na forma de uma matriz 2D de 0 “se 1” se exibirá o valor 3BV para a entrada fornecida.
Aqui está a demonstração levemente modificada no Octave para aqueles que não têm o MATLAB.
Explicação
A matriz de entrada é dilatada usando uma matriz 3 x 3 de 1 “se, em seguida, invertida (usando ~) que identifica todos os pontos que não têm minas como vizinhos (1) ou do (). Para determinar o número de regiões conectadas, usamos bwlabel para rotular cada região conectada de 1 “s. A primeira saída é a matriz de rótulo (0 onde a entrada era zero e qualquer valor no intervalo 1...N onde havia um 1 na entrada, onde N é o índice do grupo conectado ao qual pertence. A segunda saída é o número de regiões (o número de cliques necessários para abri-los). O resultado do bwlabel é mostrado na imagem à esquerda.
Expandimos a primeira saída de bwlabel usando imdilate (todos os não zeros são expandidos) usando uma matriz 3 x 3 de 1 “s. O resultado é mostrado na imagem no meio.
Para determinar os cliques restantes, contamos os quadrados que não estão nesta região expandida (~imdilate()) e não uma mina (-x) (quadrados brancos na imagem à direita) e adicione isso ao número total de regiões abertas (o número de cores diferentes na imagem à esquerda ) para obter o 3BV.
Resposta
Octave, 86 84 79 66 bytes
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) Esta solução cria uma função anônima chamada ans que pode então ser passada uma matriz 2D de 0 “se 1” s. A lógica é a mesma da minha resposta MATLAB, mas usa alguns truques que o Octave tem a oferecer para economizar espaço.
Esta solução requer que o pacote image esteja instalado .
Resposta
MATL, 24 22 21 bytes (não concorrentes )
1 byte salvo graças a @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Experimente em MATL Online
Explicação
Novamente, isso é semelhante às minhas respostas do MATLAB e do Octave para esta pergunta.
% Implicitly grab input array 4Y6 % Push the literal [1 1 1; 1 1 1; 1 1 1] to the stack Z+ % Perform 2D convolution of the input with this array ~ % Negate the result l2#ZI % Call bwlabeln which dilates each open region and the second output % returns the number of open regions w % Flip the top two stack elements 7M % Push the literal [1 1 1; 1 1 1; 1 1 1] to the stack again Z+ % Perform 2D convolution G+ % Explicitly grab the input and add it to the result ~z % Count the number of 0"s in the result (the remaining number of clicks) + % Add the total number of remaining clicks to the number of open regions Comentários
- Não concorrente por quê?
- @CalculatorFeline Infelizmente, a
bwlabelnfuncionalidade foi introduzida no MATL após o desafio foi postado.