C++ में एंड्रॉइड अनलॉक पैटर्न - वैध पैटर्न गिनें

समस्या विवरण

मान लीजिए हमारे पास एक एंड्रॉइड 3x3 कुंजी लॉक स्क्रीन है और दो पूर्णांक m और n, m और n के मान 1 ≤ m ≤ n ≤ 9 की सीमा में हैं। हमें एंड्रॉइड लॉक स्क्रीन के अनलॉक पैटर्न की कुल संख्या गिननी है, जिसमें न्यूनतम m कुंजियां और अधिकतम n कुंजियां हों।

नियम यह है कि प्रत्येक पैटर्न कम से कम m कुंजियों और अधिकतम n कुंजियों को जोड़ना चाहिए। सभी कुंजियां अद्वितीय होनी चाहिए। यदि पैटर्न में दो लगातार कुंजियों को जोड़ने वाली रेखा किसी अन्य कुंजी से गुजरती है, तो अन्य कुंजियों को पैटर्न में पहले से चुना गया होना चाहिए। किसी अनचुनी कुंजी को पार करना अनुमति नहीं है। उपयोग की गई कुंजियों का क्रम मायने रखता है।

उदाहरण के लिए, यदि m = 1, n = 1 है, तो आउटपुट 9 होगा।

समाधान दृष्टिकोण

DFS + बैकट्रैकिंग के साथ छलांग नियम:

1. आकार 10x10 की सरणी skip परिभाषित करें - छलांग नियम स्टोर करने के लिए
2. dfs() फ़ंक्शन परिभाषित करें जो नोड, लंबाई, विज़िटेड सरणी लेता है:
   • यदि लंबाई 0 है, तो 1 लौटाएं
   • विज़िटेड[नोड] := true
   • ret := 0
   • i को 1 से 9 तक लूप करें:
     • यदि विज़िटेड[i] गलत है और (skip[नोड][i] == 0 या विज़िटेड[skip[नोड][i]] सत्य है), तो ret += dfs(i, लंबाई-1, विज़िटेड)
   • विज़िटेड[नोड] := false
   • ret लौटाएं
3. मुख्य विधि से:
   • skip को 0 से भरें
   • छलांग नियम सेट करें (जैसे skip[1][3] = skip[3][1] = 2, आदि)
   • आकार 10 की विज़िटेड सरणी परिभाषित करें
   • ret := 0
   • i को m से n तक लूप करें:
     • ret += dfs(1, i-1, विज़िटेड) * 4 (कोने सममित)
     • ret += dfs(2, i-1, विज़िटेड) * 4 (किनारे सममित)
     • ret += dfs(5, i-1, विज़िटेड) (केंद्र)
   • ret लौटाएं

C++ कार्यान्वयन

#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; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.numberOfPatterns(1,1)); 
    return 0;
}

इनपुट

1, 1

आउटपुट

9