मान लीजिए हमारे पास एक एंड्रॉइड 3x3 कुंजी लॉक स्क्रीन और दो पूर्णांक एम और एन है, एम और एन के मान 1 ≤ एम ≤ एन ≤ 9 की सीमा में हैं, हमें एंड्रॉइड लॉक स्क्रीन के अनलॉक पैटर्न की कुल संख्या की गणना करनी है, जो कि न्यूनतम m कुंजियाँ और अधिकतम n कुंजियाँ शामिल हैं।
नियम इस प्रकार है, प्रत्येक पैटर्न को कम से कम m कुंजी और अधिक से अधिक n कुंजियों को जोड़ना होगा। सभी चाबियां अद्वितीय होनी चाहिए। यदि पैटर्न में लगातार दो कुंजियों को जोड़ने वाली कोई रेखा किसी अन्य कुंजी से होकर गुजरती है, तो अन्य कुंजियों को पहले पैटर्न में चुना जाना चाहिए। किसी भी कुंजी के माध्यम से कूदना जो चयनित नहीं है जिसकी अनुमति नहीं है। उपयोग की गई चाबियों का क्रम मायने रखता है।
इसलिए, यदि इनपुट m =1, n =1 जैसा है, तो आउटपुट 9
. होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
आकार की एक सरणी स्किप परिभाषित करें:10 x 10.
-
एक फ़ंक्शन को परिभाषित करें dfs(), यह नोड, लेन, एक सरणी का दौरा करेगा,
-
यदि लेन 0 के समान है, तो -
-
वापसी 1
-
-
विज़िट किया गया [नोड] :=सच
-
रिट:=0
-
इनिशियलाइज़ करने के लिए i :=1, जब i <=9, अपडेट (i से 1 की वृद्धि), करें -
-
यदि विज़िट किया गया [i] गलत है और (स्किप [नोड, i] 0 के समान है या विज़िट किया गया है [स्किप [नोड, i]] शून्य नहीं है), तो -
-
ret :=ret + dfs(i, len-1, विज़िट किया गया)
-
-
-
विज़िट किया गया [नोड] :=झूठा
-
वापसी रिट
-
मुख्य विधि से निम्न कार्य करें -
-
स्किप को 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 के आकार की देखी गई सरणी को परिभाषित करें
-
रिट:=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