C++でのAndroidのロック解除パターン

Android 3x3キーロック画面と2つの整数mとnがあり、mとnの値が1≤m≤n≤9の範囲にあるとします。Androidロック画面のロック解除パターンの総数をカウントする必要があります。最小m個のキーと最大n個のキーで構成されます。

ルールは次のようになります。各パターンは、少なくともm個のキーと最大でn個のキーを接続する必要があります。すべてのキーは一意である必要があります。パターン内の2つの連続するキーを結ぶ線が他のキーを通過する場合、他のキーはパターン内で事前に選択されている必要があります。選択されていない、許可されていないキーをジャンプします。使用するキーの順序が重要です。

したがって、入力がm =1、n =1の場合、出力は9になります

これを解決するには、次の手順に従います-

• サイズが10x10の配列スキップを定義します。

• 関数dfs（）を定義します。これにより、ノード、len、訪問された配列が取得されます。

• lenが0と同じ場合、-

  • 1を返す

• 訪問済み[ノード]：=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、訪問済み）

• 訪問済み[ノード]：=false

• retを返す

• メインの方法から、次のようにします-

• スキップを0で埋める

• 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]：=スキップ[9、1]：=5

• サイズ10の訪問済みアレイを定義する

• ret：=0

• 初期化i：=mの場合、i <=nの場合、更新（iを1増やします）、実行-

  • ret：=ret +（d​​fs（1、i-1、visited））

  • ret：=ret +（d​​fs（2、i-1、visited））

  • ret：=ret + dfs（5、i-1、訪問済み）

• 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