Android 3x3 키 잠금 화면과 두 개의 정수 m과 n이 있고 m과 n의 값이 1 ≤ m ≤ n ≤ 9 범위에 있다고 가정합니다. Android 잠금 화면의 잠금 해제 패턴의 총 수를 계산해야 합니다. 최소 m개의 키로 구성되며 최대 n개의 키로 구성됩니다.
규칙은 각 패턴이 최소 m개의 키와 최대 n개의 키를 연결해야 한다는 것과 같습니다. 모든 키는 고유해야 합니다. 패턴에서 두 개의 연속 키를 연결하는 선이 다른 키를 통과하는 경우 다른 키가 패턴에서 이전에 선택되어 있어야 합니다. 허용되지 않는 선택되지 않은 키를 통해 건너뛰기. 사용된 키의 순서가 중요합니다.
따라서 입력이 m =1, n =1과 같으면 출력은 9가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
10 x 10 크기의 배열 건너뛰기를 정의합니다.
-
dfs() 함수를 정의하면 노드, len, 방문한 배열이 필요합니다.
-
len이 0과 같으면 -
-
1 반환
-
-
방문[노드] :=참
-
ret :=0
-
initialize i :=1의 경우, i <=9일 때 업데이트(i를 1만큼 증가), −
-
Visited[i]가 거짓이고 (skip[node, i]가 0과 같거나 Visited[skip[node, i]]가 0이 아닌 경우) -
-
ret :=ret + dfs(i, len - 1, 방문)
-
-
-
방문[노드] :=false
-
리턴 렛
-
주요 방법에서 다음을 수행하십시오 -
-
건너뛰기를 0으로 채우기
-
건너뛰기[1, 3] :=건너뛰기[3, 1] :=2
-
건너뛰기[1, 7] :=건너뛰기[7, 1] :=4
-
건너뛰기[3, 9] :=건너뛰기[9, 3] :=6
-
건너뛰기[7, 9] :=건너뛰기[9, 7] :=8
-
건너뛰기[4, 6] :=건너뛰기[6, 4] :=건너뛰기[2, 8] :=건너뛰기[8, 2] :=건너뛰기[3, 7] :=건너뛰기[7, 3] :=건너뛰기[ 1, 9] :=건너뛰기[9, 1] :=5
-
크기가 10인 방문 배열을 정의합니다.
-
ret :=0
-
i:=m 초기화의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
-
ret :=ret + (dfs(1, i - 1, 방문))
-
ret :=ret + (dfs(2, i - 1, 방문))
-
ret :=ret + dfs(5, i - 1, 방문)
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int skip[10][10];
int dfs(int node, int len, vector<bool>& visited){
if (len == 0)
return 1;
visited[node] = true;
int ret = 0;
for (int i = 1; i <= 9; i++) {
if (!visited[i] && (skip[node][i] == 0 || visited[skip[node][i]])) {
ret += dfs(i, len - 1, visited);
}
}
visited[node] = false;
return ret;
}
int numberOfPatterns(int m, int n){
memset(skip, 0, sizeof(skip));
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[4][6] = skip[6][4] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[1][9] = skip[9][1] = 5;
vector<bool> visited(10);
int ret = 0;
for (int i = m; i <= n; i++) {
ret += (dfs(1, i - 1, visited) * 4);
ret += (dfs(2, i - 1, visited) * 4);
ret += dfs(5, i - 1, visited);
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.numberOfPatterns(1,1));
} 입력
1, 1
출력
9