Suponha que tenhamos uma matriz como esta:
11111
12221
12321
12221
11111
Essa matriz representa um terreno e cada célula representa uma parte do terreno. O número em cada célula representa o tempo que a parte do terreno precisa ser completamente queimada (em minutos, se for necessária uma unidade de medida), de acordo com a sua combustibilidade . Se um incêndio começa em qualquer posição (célula), essa célula precisa ser completamente queimada antes que o fogo se propague para as células adjacentes (somente horizontal e vertical, não diagonal). Portanto, se um incêndio é iniciado na posição central, ele precisa:
11111 11111 11111 11011 10001 00000
12221 3 m. 12221 2 m. 12021 1 m. 11011 1 m. 00000 1 m. 00000
12321 -----> 12021 -----> 10001 -----> 00000 -----> 00000 -----> 00000
12221 12221 12021 11011 00000 00000
11111 11111 11111 11011 10001 00000
Explicação:
- O fogo começa em [2,2] (baseado em 0), que possui um tempo de gravação de 3.
- Após 3 minutos, [1,2], [2,1], [2,3], [3,2] começam a queimar.
- Após 2 minutos, essas células terminam a queima e o fogo se propaga para todas as células adjacentes, mas [0,2], [2,0], [2,4], [0,4] precisam de apenas mais 1 minuto para queimar, portanto
- Após 1 minuto, essas células são queimadas e a célula se propaga para as células adjacentes.
- Após mais 1 minuto, o restante das células da etapa 3 termina a queima e o fogo se propaga para as células adjacentes (que já estão queimadas, para que nada aconteça).
- Após 1 último minuto, o fogo acaba queimando todo o terreno.
Portanto, a solução para esse caso é de 8 minutos. Se o fogo começar na célula superior esquerda [0,0]:
11111 01111 00111 00011 00001 00000
12221 1 12221 1 02221 1 01221 1 00121 1 00011 1
12321 --> 12321 --> 12321 --> 02321 --> 01321 --> 00321 -->
12221 12221 12221 12221 02221 01221
11111 11111 11111 11111 11111 01111
00000 00000 00000 00000 00000
00000 1 00000 1 00000 1 00000 1 00000
00221 --> 00110 --> 00000 --> 00000 --> 00000
00221 00121 00020 00010 00000
00111 00011 00001 00000 00000
Então agora o tempo total é de 10 minutos.
O desafio
Dada uma matriz NxM (N> 0, M> 0) de valores inteiros que representam o tempo que cada célula precisa ser completamente consumida, escreva o programa / função mais curto que leva essa matriz e um par de números inteiros com a posição em que o incêndio começa , e retorna / imprime o tempo necessário para que o fogo consuma completamente todo o terreno.
- Cada célula terá um tempo de gravação positivo (diferente de zero). Você não pode assumir um valor máximo para as células.
- A matriz não precisa ser quadrada nem simétrica.
- A matriz pode ser indexada em 0 ou 1, como desejar.
- A posição pode ser dada como um único parâmetro com uma tupla de números inteiros, dois parâmetros separados de qualquer outro formato razoável.
- As dimensões da matriz não podem ser especificadas como parâmetros de entrada.
- Você não precisa produzir cada etapa intermediária, apenas a quantidade de tempo solicitada. Mas não vou reclamar se as etapas forem visualizadas de alguma forma.
Outro exemplo:
Fire starts at [1,1] (a '>' represents a minute):
4253 4253 4253 4153 4043 3033 2023 0001 0000
2213 > 2113 > 2013 > 1003 > 0002 > 0001 > 0000 >> 0000 > 0000
1211 1211 1211 1111 1001 0000 0000 0000 0000
Output: 9
Este é o código-golfe , por isso o programa mais curto para cada idioma pode ganhar!
fonte
1
aM*N
Respostas:
Matlab,
235257190182178 bytesEntrada: Matriz
A
, vetor 1x2p
contendo as coordenadas de partida.Explicação:
Em vez de simular a propagação do fogo, também podemos entender isso como um problema "encontre o caminho mais curto e mais longo". A matriz é convertida em um gráfico direcionado ponderado. Os pesos dos caminhos para um único nó correspondem ao tempo para queimar o referido nó. Por exemplo, para uma matriz
temos o gráfico conectado:
Onde o nó 1 é o elemento da matriz superior esquerdo e o nó 12, o elemento inferior direito. Dadas as coordenadas iniciais
p
, o caminho mais curto para todos os outros nós é calculado. Então, o comprimento do caminho mais longo desses caminhos mais curtos + o tempo para gravar o nó inicial é igual ao tempo para gravar toda a matriz.Versão sem golfe e comentada com valores iniciais de amostra:
fonte
;
depois de cada linha. No Matlab, eles impedem que os resultados de cada comando sejam exibidos no console. Atualmente, o código é MUITO falador e gera spam no console. Mas como esse não é um estado estrito de falha, eu o mantive assim. Mas isso não importa muito, é apenas 4 bytesJavaScript (ES6),
156152146144143 bytesGuardado 1 byte graças a Kevin Cruijssen
Uma implementação bastante ingênua. Recebe entrada na sintaxe de curry
(a)(s)
, onde a é uma matriz 2D e s é uma matriz de dois números inteiros [ x, y ] representando as coordenadas baseadas em 0 da posição inicial.Formatado e comentado
Casos de teste
Mostrar snippet de código
fonte
==0
pode ser jogado<1
se não me engano.undefined<1
é falso. Obrigado!Oitava, 67 bytes
Experimente online!
Para visualizar resultados intermediários, você pode tentar isso!
Uma função que assume como matriz de entrada do terreno
a
e coordenada inicial como uma matriz de 0 e 1 com o mesmo tamanho do terreno.Na verdade, não há necessidade de,
endfunction
no entanto, executar o exemplo em que ele deve ser adicionado.Explicação:
Aplique repetidamente a dilatação da imagem morfológica no terreno e subtraia as áreas queimadas.
Resposta ungolfed:
fonte
n=1
paran=0
.MATL ,
2625 bytesO formato de entrada é:
A primeira entrada é uma matriz usando
;
como separador de linhas.A segunda entrada é um número único que aborda uma entrada da matriz na ordem principal da coluna com base em 1 (permitido pelo desafio). Por exemplo, a coordenada principal da coluna de cada entrada em uma matriz 3 × 4 é dada por
Assim, por exemplo, as coordenadas baseadas em 1 (2,2) correspondem a
5
.Experimente online! Ou verifique todos os casos de teste .
Explicação
O código mantém uma lista de entradas que estão sendo gravadas. A cada iteração, todas as entradas dessa lista são decrementadas. Quando uma entrada chega a zero, suas entradas vizinhas são adicionadas à lista. Para salvar bytes, as entradas que atingem zero não são removidas da lista; em vez disso, eles continuam "queimando" com valores negativos. O loop é encerrado quando nenhuma das entradas possui valores positivos.
Veja o programa executando passo a passo com código ligeiramente modificado.
Código comentado:
fonte
Python 2 , 170 bytes
Experimente online!
fonte
Python 3 ,
277266 bytesExperimente online!
Define uma função
f
que utiliza uma matriz 2D e uma tupla de pontos. A primeira coisa a função faz é definir um conjunto de tuplos que contêm o valor inicial tupla passou em:p={s}
. A função passa por cada tupla de pontosp
e subtrai um da matrizm
nesse ponto, a menos que o valor já seja zero. Em seguida, percorrem
novamente encontrando todos os pontos com o valor zero e adicionando os quatro vizinhos desse ponto ao conjuntop
. É por isso que escolhi usar um conjunto, porque os conjuntos em Python não permitem valores duplicados (o que estragaria bastante a subtração). Infelizmente, devido ao empacotamento do índice da lista (por exemplolist[-1] == list[len(list)-1]
:), os índices precisam ser restringidos para que não fiquem negativos e adicionem as coordenadas erradasp
.Nada de especial, ainda se acostumando ao golfe. Definitivamente espaço para melhorias aqui, eu vou continuar rachando.
fonte
APL (Dyalog) ,
936657 bytesExperimente online! ou visualize online!
Esta função toma a matriz do terreno como argumento da direita e as coordenadas (com base em 1) do primeiro disparo como argumento da esquerda. Retorna o número de minutos necessários para gravar tudo.
Atualizações
Finalmente encontrei uma maneira de jogar golfe na função spread.
* Suspiro * seria muito mais fácil se o mundo fosse toroidal .
O TIO acabou de atualizar para o Dyalog 16.0 , o que significa que agora temos o novo operador de estêncil brilhante
fonte
Python 2 , 268 bytes
Experimente online!
Faça iterações recursivas ao longo do tempo, nas quais o número de cada bloco é reduzido se for cardinalmente adjacente a um 0. Algoritmo muito simples que, acredito, ainda pode ser jogado para a eficiência booleana ...
* observação: meu 'Experimente online!' O código inclui o log de depuração de bônus no rodapé. Eu gosto de assistir o progresso do algoritmo.
fonte
Haskell ,
138133 bytesExperimente online!
Assume que a entrada é uma lista de ((x, y), célula). Ungolfed:
fonte