資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 實現 Android 解鎖圖案
假設我們有一個 Android 3x3 鍵鎖屏和兩個整數 m 和 n，m 和 n 的值範圍在 1 ≤ m ≤ n ≤ 9 之間。我們需要計算 Android 鎖屏解鎖圖案的總數，這些圖案至少包含 m 個鍵，最多包含 n 個鍵。
規則如下：每個圖案必須連線至少 m 個鍵，最多 n 個鍵。所有鍵必須是唯一的。如果連線圖案中兩個連續鍵的線穿過任何其他鍵，則其他鍵必須已在圖案中被選中。不允許跳過任何未選中的鍵。使用的鍵的順序很重要。
因此，如果輸入為 m = 1，n = 1，則輸出將為 9
為了解決這個問題，我們將遵循以下步驟：
定義一個大小為 10 x 10 的陣列 skip。
定義一個函式 dfs()，它將接收節點、長度和一個數組 visited 作為引數。
如果長度等於 0，則：
返回 1
將 visited[node] 設定為 true
ret := 0
從 i := 1 開始，當 i <= 9 時，更新（i 增加 1），執行：
如果 visited[i] 為 false 且 (skip[node, i] 等於 0 或 visited[skip[node, i]] 不為零)，則：
ret := ret + dfs(i, len - 1, visited)
將 visited[node] 設定為 false
返回 ret
從主方法執行以下操作：
用 0 填充 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
定義一個大小為 10 的陣列 visited
ret := 0
從 i := m 開始，當 i <= n 時，更新（i 增加 1），執行：
ret := ret + (dfs(1, i - 1, visited))
ret := ret + (dfs(2, i - 1, visited))
ret := ret + dfs(5, i - 1, visited)
返回 ret
示例
讓我們看下面的實現來更好地理解：
#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
1K+ 瀏覽量
