C++-এ Android Unlock Patterns: অ্যান্ড্রয়েড লক স্ক্রিনের আনলক প্যাটার্ন গণনা

অ্যান্ড্রয়েড ৩x৩ কি লক স্ক্রিন এবং দুটি ইন্টিজার m এবং n (১ ≤ m ≤ n ≤ ৯) দেওয়া আছে। কমপক্ষে m কি এবং সর্বোচ্চ n কি দিয়ে বने আনলক প্যাটার্নের মোট সংখ্যা গণনা করতে হবে।

নियमাবলী

প্রতিটি প্যাটার্ন কমপক্ষে m এবং সর্বোচ্চ n কি সংযুক্ত করবে।
সব কি ইউনিক হবে (একই কি দুবার ব্যবহার করা যাবে না)।
যদি দুটি শesia কি সংযুক্ত করার রেখা যেকোনো তৃতীয় কি ছাড়ে যায়, তবে সেই তৃতীয় কিটি প্যাটার্নে আগে থেকে নির্বাচিত থাকতে হবে। অননির্বাচিত কি লাফ দিয়ে যাওয়া যাবে না।
কি ব্যবহারের ক্রম গুরুত্বপূর্ণ।

উদাহরণ

ইনপুট: m = 1, n = 1 → আউটপুট: 9 (৯টি কি থেকে যেকোনো একটি বেছে নেওয়া যায়)।

সমাধানের পদ্ধতি (DFS + Skip Matrix)

একটি ১০x১০ skip ম্যাট্রিক্স তৈরি করুন যেখানে skip[i][j] = কি i এবং j এর মাঝপথে কোন কি আছে (যেমন skip[1][3] = 2)।
DFS ফাংশন dfs(node, len, visited) লিখুন:
- যদি len == 0, তবে ১ রিটার্ন করুন (একটি বৈধ প্যাটার্ন পাওয়া গেল)।
- visited[node] = true।
- ১ থেকে ৯ পর্যন্ত সব কি i এর জন্য:
  - যদি !visited[i] এবং (skip[node][i] == 0 বা visited[skip[node][i]]), তবে ret += dfs(i, len-1, visited)।
- visited[node] = false (ব্যাকট্র্যাক) এবং ret রিটার্ন করুন।
মেইন ফাংশনে skip ম্যাট্রিক্স ফিল করুন (সিমেট্রিক্যালি)।
m থেকে n পর্যন্ত লেন্থের জন্য:
- কর্নার কি (১,৩,৭,৯) - প্রতিটির জন্য ৪ গুণ সমান প্যাটার্ন → dfs(1, len-1) * 4।
- এজ কি (২,৪,৬,৮) - প্রতিটির জন্য ৪ গুণ → dfs(2, len-1) * 4।
- সেন্টার কি (৫) - একবার → dfs(5, len-1)।
মোট যোগফল রিটার্ন করুন।

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); // Corners
            ret += (dfs(2, i - 1, visited) * 4); // Edges
            ret += dfs(5, i - 1, visited);       // Center
        }
        return ret;
    }
};

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

ইনপুট

1, 1