Олимпиадная задача про лабиринт
Наташа решила в выходные пойти на очередной квест в реальности. Но квест оказался необычным. Наташа оказалась в лабиринте, с картой лабиринта на руках. На карте есть точка, куда она должны прийти, тогда квест считается пройденным, а за прохождение с максимальной скоростью, она получит ценный приз.
На карте отмечена точка нахождения Наташи и сам лабиринт.
Наташа очень хочет получить ценный приз, но она не знает, как проходить лабиринт быстро, потому вспомнила правило «правой руки». Она сразу же поставила правую руку на стену и пошла по лабиринту. Помогите понять, через сколько клеток Наташа сможет дойти до конечной точки, а если не сможет, то через сколько клеток она вернётся на ту же клетку, с которой начинала прохождение лабиринта.
Входные данные:
На первой строке подаётся размер лабиринта N, M (1 <= N, M <= 1000), где N – количество строк в лабиринте, M – количество столбцов.
На второй строке подаётся цифра – направление взгляда Наташи в лабиринте (от 1 до 4):
Далее на N строках подаётся по M параметров, задающих лабиринт, где
“x” – это клетка, в которую нельзя пройти;
“f” – это точка, до которой должны добраться девочки;
“1” – точка, где находится Наташа.
Выходные данные:
Вывести на одной строке – количество клеток, которое понадобится пройти Наташе, чтобы добраться до точки финиша, либо, если добраться по принципу «правой руки» невозможно, то вывести минимальное количество клеток, которые пройдёт Наташа, прежде чем вернётся в изначальную точку, с которой начинала прохождение.
Примечание:
граница всего лабиринта всегда стена;
если Наташа приходит в тупик и для разворота она кружится на месте, то это не идёт в счёт пройденных клеток;
Наташа всегда первоначально находится у стены.
Входные данные:
9 15
2
xxxxxxxxxxxxxxx
x0x10xxx000000x
x0xx0x00000000x
x0000x0xxxxxxxx
xxx0xx00000000x
x000000xxxxxxxx
x0000x00000000x
x0000x00f00000x
xxxxxxxxxxxxxxx
Выходные данные:
29
💀
def solve():
n, m = map(int, input().split())
start_direction = int(input())
labyrinth = []
for _ in range(n):
labyrinth.append(list(input()))
start_row, start_col = 0, 0
for row in range(n):
for col in range(m):
if labyrinth[row][col] == '1':
start_row, start_col = row, col
break
else:
continue
break
finish_row, finish_col = 0, 0
for row in range(n):
for col in range(m):
if labyrinth[row][col] == 'f':
finish_row, finish_col = row, col
break
else:
continue
break
directions = [(0,-1),(1,0),(0,1),(-1,0)]
visited = set()
row, col = start_row, start_col
path_len = 0
current_direction = (start_direction -1) % 4
while (row, col) != (finish_row, finish_col):
if (row,col) in visited:
print(path_len)
return
visited.add((row,col))
next_dir = (current_direction - 1 ) % 4
next_row, next_col = row + directions[next_dir][0], col + directions[next_dir][1]
if 0 <= next_row < n and 0 <= next_col < m and labyrinth[next_row][next_col] != 'x':
row, col = next_row, next_col
current_direction = next_dir
path_len +=1
continue
next_dir = current_direction
next_row, next_col = row + directions[next_dir][0], col + directions[next_dir][1]
if 0 <= next_row < n and 0 <= next_col < m and labyrinth[next_row][next_col] != 'x':
row, col = next_row, next_col
path_len+=1
continue
next_dir = (current_direction + 1) % 4
next_row, next_col = row + directions[next_dir][0], col + directions[next_dir][1]
if 0 <= next_row < n and 0 <= next_col < m and labyrinth[next_row][next_col] != 'x':
row, col = next_row, next_col
current_direction = next_dir
path_len +=1
continue
current_direction = (current_direction + 2) % 4
print(path_len)
solve()