C++ এ অ্যান্ড্রয়েড আনলক প্যাটার্ন

ধরুন আমাদের একটি অ্যান্ড্রয়েড 3x3 কী লক স্ক্রিন এবং দুটি পূর্ণসংখ্যা m এবং n আছে, m এবং n এর মান 1 ≤ m ≤ n ≤ 9 রেঞ্জে রয়েছে, আমাদের Android লক স্ক্রিনের আনলক প্যাটার্নের মোট সংখ্যা গণনা করতে হবে, যা সর্বনিম্ন m কী এবং সর্বোচ্চ n কীগুলি নিয়ে গঠিত।

নিয়মটি হল, প্রতিটি প্যাটার্নকে কমপক্ষে m কী এবং সর্বাধিক n কীগুলিকে সংযুক্ত করতে হবে। সমস্ত কী অনন্য হতে হবে. যদি প্যাটার্নে পরপর দুটি কী সংযোগকারী একটি লাইন থাকে যা অন্য কোন কীগুলির মধ্য দিয়ে যায়, তবে অন্যান্য কীগুলি অবশ্যই প্যাটার্নে আগে নির্বাচন করা থাকতে হবে। যে কোন চাবির মাধ্যমে জাম্প করা অনুমোদিত নয় যেটি নির্বাচন করা হয়নি। ব্যবহৃত চাবিগুলির ক্রম বিষয়গুলি।

সুতরাং, যদি ইনপুট হয় m =1, n =1, তাহলে আউটপুট হবে 9

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• আকারের একটি অ্যারে স্কিপ সংজ্ঞায়িত করুন:10 x 10।

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি নোড, লেন, একটি অ্যারে পরিদর্শন করবে,

• যদি লেন 0 এর মত হয়, তাহলে −

  • রিটার্ন 1

• পরিদর্শন [নোড] :=সত্য

• ret :=0

• আরম্ভ করার জন্য i :=1, যখন i <=9, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • যদি পরিদর্শন করা হয় [i] মিথ্যা হয় এবং (skip[node, i] 0 এর মত হয় বা পরিদর্শন করা [skip[node, i]] হয় nonzero), তাহলে −

    • 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 আকারের পরিদর্শন করা একটি অ্যারের সংজ্ঞায়িত করুন

• 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