Jogos de táticas baseadas em turnos, como Advance Wars, Wargroove e Fire Emblem, são constituídos por uma grade quadrada de terreno variável, com unidades de diferentes classes de movimento, exigindo custos diferentes para cada tipo de terreno. Investigaremos um subconjunto desse problema.
Desafio
Sua tarefa é determinar se um local é acessível a partir de outro, dada uma grade de custos do terreno e uma velocidade de movimento.
As unidades só podem se mover ortogonalmente onde o custo de se mover para um quadrado é o valor da célula correspondente na grade (a saída é gratuita). Por exemplo, mover de uma célula com valor 3 para uma célula com valor 1 custa 1 movimento, mas seguir o caminho requer 3. Alguns quadrados podem estar inacessíveis.
Exemplo
1 [1] 1 1 1
1 2 2 3 1
2 3 3 3 4
1 3 <1> 3 4
Mover de [1]
para <1>
requer um mínimo de 7 pontos de movimento, movendo para a direita um quadrado e depois para baixo três. Assim, se for dada 6 ou menos como velocidade de movimento, você deverá emitir uma resposta falsa.
Casos de teste de exemplo
Eles usarão coordenadas com índice zero (linha, coluna) de origem superior esquerda, em vez de células entre colchetes, no início e no final, para facilitar a análise. As células inacessíveis serão representadas comX
Caso 1a
1 1 2 1 X
1 2 2 1 1
2 1 1 2 1
X X X 1 2
Speed: 5
From (2, 3) to (0, 1)
Output: True
Caso 1b
1 1 2 1 X
1 2 2 1 1
2 1 1 2 1
X X X 1 2
Speed: 4
From (2, 3) to (0, 1)
Output: False
Caso 1c
1 1 2 1 X
1 2 2 1 1
2 1 1 2 1
X X X 1 2
Speed: 5
From (0, 1) to (2, 3)
Output: False
Caso 2a
3 6 1 1 X 4 1 2 1 X
5 1 2 2 1 1 1 X 1 5
2 1 1 1 2 1 1 1 X 1
2 1 1 3 1 2 3 4 1 2
1 1 2 1 1 4 1 1 1 2
3 2 3 5 6 1 1 X 1 4
Speed: 7
From (3, 4) to (2, 1)
Output: True
Caso 2b
3 6 1 1 X 4 1 2 1 X
5 1 2 2 1 1 1 X 1 5
2 1 1 1 2 1 1 1 X 1
2 1 1 3 1 2 3 4 1 2
1 1 2 1 1 4 1 1 1 2
3 2 3 5 6 1 1 X 1 4
Speed: 4
From (3, 4) to (2, 1)
Output: False
Caso 2c
3 6 1 1 X 4 1 2 1 X
5 1 2 2 1 1 1 X 1 5
2 1 1 1 2 1 1 1 X 1
2 1 1 3 1 2 3 4 1 2
1 1 2 1 1 4 1 1 1 2
3 2 3 5 6 1 1 X 1 4
Speed: 7
From (1, 8) to (2, 7)
Output: True
Caso 3a
2 1 1 2
2 3 3 1
Speed: 3
From (0, 0) to (1, 1)
Output: False
Caso 3b
2 1 1 2
2 3 3 1
Speed: 3
From (1, 1) to (0, 0)
Output: True
Regras, premissas e notas
- As brechas padrão são proibidas, a E / S pode estar em qualquer formato conveniente
- Você pode assumir que as coordenadas estão todas na grade
- A velocidade de movimento nunca será superior a 100
- As células inacessíveis podem ser representadas com números muito grandes (por exemplo, 420, 9001, 1 milhão) ou com 0 ou nulo, o que for mais conveniente para você.
- Todas as entradas consistirão em números inteiros positivos (a menos que seja nulo ou 0 para representar células inacessíveis)
fonte
Respostas:
Consulta TSQL,
205191 bytesInput é uma variável de tabela @t
@ x = iniciar xpos, @ y = iniciar ypos @ i = final xpos, @ j = final ypos @ = velocidade
Experimente a versão online não destruída
fonte
Python 2 , 220 bytes
Experimente online!
Leva uma matriz
m
de números inteiros, com'X'
como um valor maior do que a 100 ;, uma velocidadea
,m
que tem larguraw
e alturah
; e retorna quando pudermos começar na célula de linha / coluna indexada a zero(r,c)
e chegar à célula final(R,C)
.O algoritmo é um preenchimento modificado. Código ligeiramente não destruído:
fonte
JavaScript (ES7),
116113 bytesToma entrada como0 1
(matrix)([endRow, endCol])(speed, startRow, startCol)
. Espera grandes valores para quadrados inacessíveis. Retorna ou .Experimente online!
Comentado
fonte
Geléia , 59 bytes
Experimente online!
Não é terrivelmente rápido; tenta todos os caminhos até que as unidades de velocidade se esgotem, refazendo seus passos. No entanto, isso evita a necessidade de verificar se os espaços são visitados. A entrada é fornecida como
[nrows, ncols],[start_row, start_col],[end_row, end_col],speed,flattened matrix column-major
Explicação
Link auxiliar
Link principal
fonte
Gelatina , 38 bytes
Um programa completo extremamente ineficiente que aceita o terreno (com os invisíveis como 101), em seguida, o início e o fim coordenam a velocidade.
Experimente online! (não faz muito sentido tentar a maioria dos casos de teste!)
Quão?
Cria uma lista de todas as permutações de cada um dos conjuntos de potência de "locais para todos os terrenos, exceto o início e o fim", envolve cada um deles com o início e o fim, filtros para aqueles que fazem apenas movimentos ortogonais da distância um, diminuem o início de cada um, indexa de volta ao terreno, soma cada um, pega o mínimo, subtrai um e testa que isso é menor que a velocidade.
fonte