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

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 = -1, -1
    finish_row, finish_col = -1, -1
 
    for r in range(n):
        for c in range(m):
            if labyrinth[r][c] == '1':
                start_row, start_col = r, c
            elif labyrinth[r][c] == 'f':
                finish_row, finish_col = r, c
 
    current_row, current_col = start_row, start_col
    current_direction = start_direction
    visited = set()
    steps = 0
 
    while True:
        visited.add((current_row, current_col))
        steps += 1
 
        if current_row == finish_row and current_col == finish_col:
            print(steps)
            return
 
        # Find next cell using right-hand rule
        next_row, next_col = current_row, current_col
        found_next = False
        for i in range(4):
            next_direction = (current_direction + i) % 4
            if next_direction == 0:  # Up
                next_row = current_row - 1
                next_col = current_col
            elif next_direction == 1:  # Down
                next_row = current_row + 1
                next_col = current_col
            elif next_direction == 2:  # Left
                next_row = current_row
                next_col = current_col - 1
            elif next_direction == 3:  # Right
                next_row = current_row
                next_col = current_col + 1
 
            if 0 <= next_row < n and 0 <= next_col < m and labyrinth[next_row][next_col] != 'x':
                current_row, current_col = next_row, next_col
                current_direction = next_direction
                found_next = True
                break
 
        if not found_next:  # If we are in a dead end
            if (current_row, current_col) == (start_row, start_col) and steps > 1:
                print(steps)
                return
 
            # Try to turn around
            current_direction = (current_direction + 2) % 4  # Turn 180 degrees
 
 
solve()

def right_hand_rule(labyrinth, start_pos, start_dir):
    # Определяем направления: 1 - вверх, 2 - вправо, 3 - вниз, 4 - влево
    directions = {
        1: (-1, 0),  # вверх
        2: (0, 1),  # вправо
        3: (1, 0),  # вниз
        4: (0, -1)  # влево
    }
 
    # Повороты направлений (правый поворот)
    right_turn = {
        1: 2,
        2: 3,
        3: 4,
        4: 1
    }
 
    # Повороты направлений (левый поворот)
    left_turn = {
        1: 4,
        2: 1,
        3: 2,
        4: 3
    }
 
    # Установим начальные значения
    current_pos = start_pos
    current_dir = start_dir
    visited = set()  # Множество для хранения посещенных клеток
    steps = 0
 
    while True:
        if current_pos in visited:
            return steps, "loop"  # Вернуться в исходную точку
 
        visited.add(current_pos)
 
        # Проверка на достижение финиша
        if labyrinth[current_pos[0]][current_pos[1]] == 'f':
            return steps, "finish"
 
        # Определяем новое направление по правой руке
        right_direction = right_turn[current_dir]
 
        # Проверяем возможность движения в направлении "правой руки"
        right_move = (current_pos[0] + directions[right_direction][0],
                      current_pos[1] + directions[right_direction][1])
 
        if labyrinth[right_move[0]][right_move[1]] != 'x':  # Если можно пройти
            current_pos = right_move
            current_dir = right_direction
            steps += 1
        else:
            # Если нельзя пройти, поворачиваем налево
            current_dir = left_turn[current_dir]
            # Проверяем движение вперед по текущему направлению
            forward_move = (current_pos[0] + directions[current_dir][0],
                            current_pos[1] + directions[current_dir][1])
 
            if labyrinth[forward_move[0]][forward_move[1]] != 'x':  # Если можно пройти
                current_pos = forward_move
                steps += 1
            else:
                # Если никуда не можем пойти, остаемся на месте (не учитываем шаг)
                continue
 
 
# Чтение входных данных
N, M = map(int, input().strip().split())
start_direction = int(input().strip())
labyrinth =[list(input().strip()) for _ in range(N)]
 
# Поиск начальной позиции Наташи
start_pos = None
 
for i in range(N):
    for j in range(M):
        if labyrinth[i][j] == '1':
            start_pos = (i, j)
            break
    if start_pos:
        break
 
# Запускаем алгоритм
steps, result_type = right_hand_rule(labyrinth, start_pos, start_direction)
 
if result_type == "finish":
    print(steps)
else:
    print(steps)

def main():
    import sys
    from collections import deque
 
    # Чтение входных данных
    N, M = map(int, sys.stdin.readline().split())
    direction = int(sys.stdin.readline())
    maze =[list(sys.stdin.readline().strip()) for _ in range(N)]
 
    # Находим начальную позицию Наташи
    start_pos = None
    for i in range(N):
        for j in range(M):
            if maze[i][j] == '1':
                start_pos = (i, j)
                break
        if start_pos:
            break
 
    # Направления: 1 - вверх, 2 - вправо, 3 - вниз, 4 - влево
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    dir_idx = direction - 1
 
    # Начальная позиция и направление
    x, y = start_pos
    visited = set()
    steps = 0
 
    while True:
        if (x, y) in visited:
            # Если вернулись в начальную точку, выводим количество шагов
            print(steps)
            return
        visited.add((x, y))
 
        # Проверяем, достигли ли мы финиша
        if maze[x][y] == 'f':
            print(steps)
            return
 
        # Пытаемся двигаться вперёд
        nx, ny = x + directions[dir_idx][0], y + directions[dir_idx][1]
        if 0 <= nx < N and 0 <= ny < M and maze[nx][ny] != 'x':
            x, y = nx, ny
            steps += 1
        else:
            # Если нельзя двигаться вперёд, поворачиваем направо
            dir_idx = (dir_idx + 1) % 4
 
if __name__ == "__main__":
    main()