Олимпиадная задача про лабиринт

Question

Олимпиадная задача про лабиринт

Аркадий Паровозов Ученик (59), на голосовании 6 дней назад

Наташа решила в выходные пойти на очередной квест в реальности. Но квест оказался необычным. Наташа оказалась в лабиринте, с картой лабиринта на руках. На карте есть точка, куда она должны прийти, тогда квест считается пройденным, а за прохождение с максимальной скоростью, она получит ценный приз.

На карте отмечена точка нахождения Наташи и сам лабиринт.

Наташа очень хочет получить ценный приз, но она не знает, как проходить лабиринт быстро, потому вспомнила правило «правой руки». Она сразу же поставила правую руку на стену и пошла по лабиринту. Помогите понять, через сколько клеток Наташа сможет дойти до конечной точки, а если не сможет, то через сколько клеток она вернётся на ту же клетку, с которой начинала прохождение лабиринта.

Входные данные:

На первой строке подаётся размер лабиринта 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

Answer 1

Сергей Яговцев Профи (662) 1 месяц назад

?

Аркадий ПаровозовУченик (59) 1 месяц назад

10 класс если что)

Answer 2

 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()