Editorial for Hoppers of Middle Earth

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Türkçe

Problem bir graph traversal algoritması kullanılarak çözülebilir. Alandaki her konumun/noktanın bir node ve her noktadan tüm hoplamaların yönü ve mesafesi ile edge'ler olduğunu düşünebilirsiniz.

Verilen çözümde BFS algoritmasını kullandık (Binary First Search). Ersel'in vardığı her nokta için \(\mathbf{K}\) hopper'ı kullanabilir ve farklı noktalara hoplayabilir. Hoplayabileceği noktalar arasında daha önce gitmediği bir nokta varsa, o nokta queue'ya eklenir. Bu arada bahsi geçen noktanın mesafesi de güncellenir.

English

The problem can be solved using a graph traversal algorithm. You can think as the cells/locations are nodes and there are edges from each cell with each hopper's direction and distance.

In the given solution, we have used the BFS algorithm (Binary First Search). Ersel can use the \(\mathbf{K}\) different hoppers for each cell he arrives at, and he can travel to the cells he can hop. If there is a cell he hasn't traveled between the cells, he can hop to that cell is added to the queue. The mentioned cell's distance is also updated in the meantime.

from collections import deque

N, M = map(int, input().strip().split(" "))
field = []

for i in range(N):
    field.append(list(input().strip()))

K = int(input())
moves = []
direction = {
    'W': (0, -1),
    'E': (0, 1),
    'N': (-1, 0),
    'S': (1, 0)
}

for i in range(K):
    dirr, dist = input().strip().split(" ")
    moves.append((direction[dirr][0] * int(dist), direction[dirr][1] * int(dist)))


sx, sy = -1, -1
ex, ey = -1, -1

distance = []
for i in range(N):
    distancecur = []
    for j in range(M):
        if field[i][j] == 'A':
            sx = i
            sy = j
            distancecur.append(0)
        elif field[i][j] == 'Z':
            ex = i
            ey = j
            distancecur.append(-1)
        elif field[i][j] == '*':
            distancecur.append(-2)
        else:
            distancecur.append(-1)
    distance.append(distancecur)

result = -1
q = deque()
q.append((0, sx, sy))

while len(q) > 0:
    cost, x, y = q.popleft()

    if x == ex and y == ey:
        result = cost
        break

    for xinc, yinc in moves:
        xx, yy = x + xinc, y + yinc

        if 0 <= xx < N and 0 <= yy < M and distance[xx][yy] == -1:
            q.append((cost+1, xx, yy))
            distance[xx][yy] = cost + 1

print(result)