СРОЧНО ПАЙТОН D. Игра-платформер
Вы разрабатываете игру-платформер. Игровое поле может быть представлено как бесконечная клетчатая полоска,
каждая клетка которой занумерована целым числом как на картинке ниже. Изначально игрок находится в позиции 0 и смотрит вправо.
На вход вашей программе подается последовательность команд — движения игрока. Они могут быть трех типов:
F - Forward - Движение вперед в текущем направлении
R - Right - Поворот направо
L - Left - Поворот налево
При этом разрешается несколько раз выполнять один и тот же поворот,
например, «LL». После такой последовательности команд игрок будет смотреть влево.
Вы нашли уязвимость в игре и получили последовательность действий вашего друга.
Вам известно, что перехваченная вами последовательность отличается от настоящей ровно в одном символе.
Найдите все позиции,
в которых мог на самом деле оказаться ваш друг после выполнения всех действий.
Формат ввода
В первой строке ввода находится единственное целое число N количество команд.
Во второй строке находятся N символов — сами команды.
Гарантируется, что все символы принадлежат множеству {«F»,«R»,«L»}.
Формат вывода
Выведите единственное число — количество различных позиций, на которых мог оказаться игрок после выполнения всех действий.
def calculate_positions(commands):
possible_position = set()
possible_commands = []
for i in range(len(commands)):
if commands[i] == 'L':
possible_cmd = replace_char_at_index(commands, i, 'F')
possible_commands.append(possible_cmd)
possible_cmd = replace_char_at_index(commands, i, 'R')
possible_commands.append(possible_cmd)
if commands[i] == 'R':
possible_cmd = replace_char_at_index(commands, i, 'F')
possible_commands.append(possible_cmd)
possible_cmd = replace_char_at_index(commands, i, 'L')
possible_commands.append(possible_cmd)
if commands[i] == 'F':
possible_cmd = replace_char_at_index(commands, i, 'R')
possible_commands.append(possible_cmd)
possible_cmd = replace_char_at_index(commands, i, 'L')
possible_commands.append(possible_cmd)
for cmd in possible_commands:
position = 0
direction = 'R'
for do in cmd:
if do == 'R':
direction = 'R'
if do == 'L':
direction = 'L'
if do == 'F':
if direction == 'R':
position += 1
else:
position -= 1
possible_position.add(position)
return len(possible_position)
def replace_char_at_index(s, index, new_char):
if index < 0 or index >= len(s):
raise ValueError("Index out of range")
return s[:index] + new_char + s[index+1:]
N = int(input())
commands = input().strip()
result = calculate_positions(commands)
print(result) Я решил так, но уперся в потребление памяти
Меня тоже интересует решение этой задачи, особенно беспокоит вопрос, возможно ли её решить быстрее чем за O(n^2) ?
def final_positions_count(N, commands):
def move(commands):
x = 0
direction = 0 # 0 - right, 1 - down, 2 - left, 3 - up
for command in commands:
if command == 'F':
if direction == 0:
x += 1
elif direction == 2:
x -= 1
elif command == 'R':
direction = (direction + 1) % 4
elif command == 'L':
direction = (direction - 1) % 4
return x
unique_positions = set()
for i in range(N):
for replacement in 'FRL':
if commands[i] != replacement:
new_commands = commands[:i] + replacement + commands[i+1:]
position = move(new_commands)
unique_positions.add(position)
return len(unique_positions)
# Чтение входных данных
N = int(input())
commands = input().strip()
# Вычисление и вывод результата
print(final_positions_count(N, commands))