Один из способов разблокировать телефон Android - использовать комбинацию ударов по клавиатуре 1-9.
Чтобы шаблон был действительным, он должен удовлетворять следующим условиям:
- Все его ключи должны быть различны.
- Он не должен соединять две клавиши, перепрыгивая через третью клавишу, если только эта клавиша не была использована.
Например, 4 - 2 - 1 - 7 - действительный шаблон, тогда как 2 - 1 - 7 - нет.
Найдите общее количество действительных шаблонов разблокировки длиной N, где 1 <= N <= 9.
Invalid ход: 4 - 1 - 3 - 6
Строка 1 - 3 проходит через ключ 2, который не был выбран в шаблоне.
Недопустимый ход: 4 - 1 - 9 - 2
Строка 1 - 9 проходит через ключ 5, который не был выбран в шаблоне.
Допустимое перемещение: 2 - 4 - 1 - 3 - 6
Строка 1 - 3 действительна, поскольку она проходит через ключ 2, который был выбран в шаблоне
Допустимое движение: 6 - 5 - 4 - 1 - 9 - 2
Строка 1 - 9 действительна, поскольку она проходит через ключ 5, который ch был выбран в шаблоне.
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Я могу решить проблему с помощью DFS. Но мы также должны рассмотреть пропуск / прыжок. Для решения этой проблемы я видел людей, которые сохраняли / использовали только следующие комбинации правильных прыжков.
, например,
int skip[][] = new int[10][10];
skip[1][3] = skip[3][1] = 2;
skip[1][7] = skip[7][1] = 4;
skip[3][9] = skip[9][3] = 6;
skip[7][9] = skip[9][7] = 8;
skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
Может кто-нибудь помочь объяснить, почему следующая комбинация не включена в skip / jump?
skip[1][6] = skip[6][1] = 2;
skip[1][6] = skip[6][1] = 5;
Пример https://medium.com/@rebeccahezhang / leetcode-351- android -unlock-Pattern-d9bae4a8a958