Решение задачи python "Графический пароль"

Question

Решение задачи python "Графический пароль"

Никита Кузьминых Знаток (266), открыт 2 дня назад

Графический пароль
Во многих смартфонах для задания пароля используется графический ключ. Чтобы разблокировать устройство, вам нужно соединить последовательность точек в сетке, проводя пальцем по экрану, не отрывая его.
На изображении ниже приведен пример рисунка из 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

Дополнен 2 дня назад

Можно выполнять и на других языках,но рекомендуется python

Answer 1

Авторы этого "графического ключа" - лютые изверги. Однако есть один нюанс, программы для смартфонов на Питоне в жизнь никогда не писали

Answer 2

Вот так вот

 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