Алгоритм с использованием рекурсивной функции
https://codeup.kr/problem.php?id=6098
Привет, дорогой! Прошу вашего драгоценного совета.. Спасибо за совет
[Правило: Постановка проблемы]
- начальная точка: (1,1)
- Только перейти к 0
- Должно двигаться вправо(0,1) или вниз(1,0) (* Движение вправо всегда предпочтительнее движения вниз)
- Двигайтесь до встречи 2 или не можете двигаться в любом направлении.
- Отметьте пройденный путь цифрой 9.
Я ожидал вывода A, но мой код напечатал неправильный вывод, B. Я не знаю, почему.
Говоря подробно, я ожидал, что «перерыв» сработает в (6,6), но этого не произошло. После перехода (7,6) все нули наконец меняются на 9. Это неправильный результат... Другими словами, третий «элиф» не работает.
Подскажите пожалуйста как исправить..
[A]
1 1 1 1 1 1 1 1 1 1
1 9 9 1 0 0 0 0 0 1
1 0 9 1 1 1 0 0 0 1
1 0 9 9 9 9 9 1 0 1
1 0 0 0 0 0 9 1 0 1
1 0 0 0 0 1 9 1 0 1
1 0 0 0 0 1 9 1 0 1
1 0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
[B]
1 1 1 1 1 1 1 1 1 1
1 9 9 1 9 9 9 9 9 1
1 0 9 1 1 1 9 9 9 1
1 9 9 9 9 9 9 1 9 1
1 9 9 9 9 9 9 1 9 1
1 9 9 9 9 1 9 1 9 1
1 9 9 9 9 1 9 1 9 1
1 9 9 9 9 1 9 9 9 1
1 9 9 9 9 9 9 9 9 1
1 1 1 1 1 1 1 1 1 1
[Initial grid]
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 0 0 1
1 0 0 1 1 1 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 1 0 1 0 1
1 0 0 0 0 1 2 1 0 1
1 0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
[output; In fact, It should stop in (6,6)]
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 0 0 1
1 0 0 1 1 1 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 1 0 1 0 1
1 0 0 0 0 1 2 1 0 1
1 0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
1 1
1 2
2 2
3 2
3 3
3 4
3 5
3 6
4 6
5 6
6 6
7 6
7 7
7 8
8 8
8 8
7 8
8 7
7 7
8 7
7 8
8 6
6 7
6 8
7 8
8 8
6 8
7 6
8 6
7 7
8 6
4 7
4 8
5 8
6 8
7 8
8 8
5 8
6 8
7 8
8 8
4 8
5 6
6 6
7 6
8 6
3 7
3 8
4 8
5 8
6 8
7 8
8 8
3 8
4 6
5 6
6 6
7 6
8 6
3 6
4 5
5 5
6 5
7 5
8 5
7 6
8 5
3 5
4 5
5 5
6 5
7 5
8 5
3 6
4 4
5 4
6 4
7 4
8 4
7 5
8 4
6 5
7 4
8 4
5 5
6 4
7 4
8 4
4 5
5 4
6 4
7 4
8 4
3 4
4 4
5 4
6 4
7 4
8 4
3 5
4 3
5 3
6 3
7 3
8 3
7 4
8 3
6 4
7 3
8 3
5 4
6 3
7 3
8 3
4 4
5 3
6 3
7 3
8 3
3 3
4 3
5 3
6 3
7 3
8 3
3 4
4 2
5 2
6 2
7 2
8 2
7 3
8 2
6 3
7 2
8 2
5 3
6 2
7 2
8 2
4 3
5 2
6 2
7 2
8 2
2 3
3 2
4 2
5 2
6 2
7 2
8 2
3 3
4 2
5 2
6 2
7 2
8 2
1 3
1 4
1 5
1 6
1 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
8 8
2 8
3 8
4 8
5 8
6 8
7 8
8 8
1 8
2 7
3 7
4 7
5 7
6 7
7 7
8 7
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
1 8
2 6
3 6
4 6
5 6
6 6
7 6
8 6
1 6
2 6
3 6
4 6
5 6
6 6
7 6
8 6
1 7
2 5
3 5
4 5
5 5
6 5
7 5
8 5
1 5
2 4
3 4
4 4
5 4
6 4
7 4
8 4
1 4
2 2
3 2
4 2
5 2
6 2
7 2
8 2
1 2
2 1
3 1
4 1
5 1
6 1
7 1
8 1
7 2
8 1
6 2
7 1
8 1
5 2
6 1
7 1
8 1
4 2
5 1
6 1
7 1
8 1
3 2
4 1
5 1
6 1
7 1
8 1
2 2
3 1
4 1
5 1
6 1
7 1
8 1
[Мой код]
grid = []
for i in range(10):
grid.append([])
for j in range(10):
grid[i].append(0)
for i in range(10):
grid[i] = list(map(int, input().split()))
p_x, p_y = (1,1)
grid[p_x][p_y] = 9
def move(p_x, p_y):
for x in range(p_x,9):
for y in range(p_y,9):
print(x,y)
if grid[x][y + 1] == 0:
grid[x][y + 1] = 9
move(x, y + 1)
elif grid[x][y + 1] == 2:
grid[x][y + 1] = 9
break
elif grid[x + 1][y] == 0:
grid[x + 1][y] = 9
move(x + 1, y)
elif grid[x + 1][y] == 2:
grid[x + 1][y] = 9
break
else:
break
move(p_x, p_y)
Какой у Вас вопрос?
@deceze Я добавил логику. Спасибо!
Я не знаю, почему все нули заменены на 9. Я ожидал результата A. Для этого код должен перестать работать в (6,6), но это не так. @MUYБельгия
Можете ли вы предоставить формулировку проблемы на английском языке?
Я написал формулировку проблемы выше~ Я дам вам знать, если вы скажете мне, в какой части, по вашему мнению, объяснение недостаточно. @Полный
@유한정 Неясно, когда разрешено движение вниз.
@ Перемещение разрешено, если установлено значение 0. Кроме того, перемещение разрешено только вправо или вниз. Я только что обнаружил свою ошибку и исправил ее («влево» -> «вниз»). @Полный
@유한정 Всегда ли движение вправо предпочтительнее движения вниз, когда оба варианта возможны?
@Unmitigated Извините, я пропустил этот момент. Движение вправо всегда предпочтительнее движения вниз.
Ответы 3
Вместо того, чтобы перебирать значения x и y в определенном диапазоне, просто попробуйте каждое движение по порядку и выполните рекурсивный вызов move для следующего местоположения, который правильно отслеживает текущее местоположение.
def move(p_x, p_y):
for dx in range(2):
if grid[p_x + dx][p_y + 1 - dx] == 2:
grid[p_x + dx][p_y + 1 - dx] = 9
break
elif grid[p_x + dx][p_y + 1 - dx] == 0:
grid[p_x + dx][p_y + 1 - dx] = 9
return move(p_x + dx, p_y + 1 - dx)
Будет эффективнее переписать это с помощью итерации.
Большое спасибо ! Вы случайно не сообщите мне, почему мой код работает неправильно? (почему мой «перерыв» не работает) ..? @Полный
@유한정 Вам придется дважды прервать выполнение, чтобы выйти из двух слоев циклов for. Кроме того, неясно, почему вы перебираете все эти позиции вместо того, чтобы просто проверять два возможных хода.
Некоторые вопросы:
Вы смешиваете итерацию и рекурсию, так что даже если вы нашли путь решения с помощью внутреннего вызова move(), выполнение все равно продолжает цикл, в котором был сделан этот вызов move(). Вам надо "уйти оттуда" ;-)
Кроме того, операторы break выходят только из внутреннего цикла, а не из внешнего. В результате вы продолжите писать больше девяток в сетке, даже если уже нашли цель.
Но поскольку вы используете рекурсию, вам не нужно перебирать разные значения x и y. Следует рассматривать только альтернативный ход (вниз, а не вправо).
Теперь для данной сетки вы можете «жадно» искать хороший путь, но это может быть неверно для других сеток, например этой:
grid = [
[1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1],
[1, 0, 2, 0, 0, 1],
[1, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1],
]
Для этого вам необходимо реализовать возврат, то есть, когда рекурсивный вызов не может добраться до цели, попробуйте альтернативный ход с другим рекурсивным вызовом:
def move(x, y):
if grid[x][y] != 0: # not free
return grid[x][y] == 2 # True if it is the target
grid[x][y] = 9 # visit
for x1, y1 in ((x, y + 1), (x + 1, y)):
if move(x1, y1) :
return True # Propagate the success back to the caller
grid[x][y] = 0 # Apparently the wrong way, so undo (backtrack)
p_x, p_y = (1, 1)
# don't mark with 9 yet here.
if move(p_x, p_y): # Found a path!
for row in grid:
print(row)
else:
print("No path found.")
Хороший ответ. ОП, наверное, хотел написать grid[y][x], а не grid[x][y]. Я добавил пост, в котором показано, как изменить вашу программу move, чтобы перечислить все решения.
Дополнение к ответу @trincot. Вы можете легко изменить move, чтобы перечислить все возможные решения для данной отправной точки —
def move(x, y):
try:
match grid[y][x]:
case 2:
yield # solution found
case 0:
grid[y][x] = 9 # visit
yield from move(x, y + 1)
yield from move(x, y - 1)
yield from move(x + 1, y)
yield from move(x - 1, y)
grid[y][x] = 0 # unvisit
except IndexError:
pass
Теперь move выдает повторяемый результат вместо простого True или False. Запустите программу, чтобы увидеть все 131 решение —
for (n, _) in enumerate(move(1, 1)):
print(f"solution {n}")
for row in grid:
print(row)
Пожалуйста, объясните логику ожидаемого результата.