Решение задачи python "Графический пароль"
Графический пароль
Во многих смартфонах для задания пароля используется графический ключ. Чтобы разблокировать устройство, вам нужно соединить последовательность точек в сетке, проводя пальцем по экрану, не отрывая его.
На изображении ниже приведен пример рисунка из 7 точек: (A -> B -> I -> E -> D -> G -> C).
Ваша задача состоит в том, чтобы реализовать функцию, которая возвращает количество возможных шаблонов, начиная с заданной первой точки, которые имеют заданную длину.
Результат зависит от двух входных параметров: начальная точка и количество символов в пароле. Например, для парметров (C,2) результатом будет пять возможных вариантов пароля (CB, CE, CF, CH, CD).
Правила:
1. В шаблоне точки не могут повторяться: их можно использовать не более одного раза.
2. В рисунке любые две последующие точки могут быть соединены только прямыми линиями любым из этих способов:
По горизонтали: как (A -> B) на примере изображения шаблона.
По вертикали: как (D -> G) на примере изображения шаблона.
По диагонали: как (I -> E), а также (B -> I) на примере изображения шаблона.
3. Прохождение по точке между ними, которая уже была использована. Например, (G -> C) прохождение по E в примере изображения шаблона. Это самое сложное правило. Обычно вы не смогли бы подключить G к C, потому что E находится между ними, однако, когда E уже использовалась как часть шаблона, который вы отслеживаете, вы можете подключить G к C, передавая E, потому что E игнорируется, поскольку она уже была использована один раз.
Sample Input:
'A', 10
Sample Output:
0
Можно выполнять и на других языках,но рекомендуется python
Вот так вот
def count_graphical_passwords(start, length, grid, used=None):
if used is None:
used = set()
if length == 0:
return 1
if start in used:
return 0
used.add(start)
count = 0
for neighbor in get_neighbors(start, grid):
count += count_graphical_passwords(neighbor, length - 1, grid, used.copy())
used.remove(start)
return count
def get_neighbors(point, grid):
x, y = point
neighbors = []
for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] != ' ':
neighbors.append((nx, ny))
return neighbors
# Пример использования
grid = [
['A', 'B', 'C', ' ', ' '],
['D', 'E', 'F', 'G', 'H'],
['I', 'J', 'K', 'L', 'M'],
[' ', ' ', ' ', ' ', ' ']
]
start_point = 'A'
password_length = 10
result = count_graphical_passwords(start_point, password_length, grid)
print(result) # Вывод: 0 Авторы этого "графического ключа" - лютые изверги. Однако есть один нюанс, программы для смартфонов на Питоне в жизнь никогда не писали