รูปแบบการปลดล็อก Android ใน C ++

สมมติว่าเรามีหน้าจอล็อกปุ่ม Android 3x3 และจำนวนเต็มสองจำนวน m และ n ค่าของ m และ n อยู่ในช่วง 1 ≤ m ≤ n ≤ 9 เราต้องนับจำนวนรูปแบบการปลดล็อกทั้งหมดของหน้าจอล็อก Android ซึ่ง ประกอบด้วยคีย์ขั้นต่ำ m และสูงสุด n คีย์

กฎคือ แต่ละรูปแบบต้องเชื่อมต่ออย่างน้อย m คีย์ และ มากที่สุด n คีย์ คีย์ทั้งหมดต้องไม่ซ้ำกัน หากมีเส้นที่เชื่อมระหว่างปุ่มสองปุ่มที่ต่อเนื่องกันในรูปแบบผ่านปุ่มอื่นๆ คีย์อื่นๆ จะต้องเลือกไว้ในรูปแบบก่อนหน้านี้ ข้ามผ่านคีย์ใด ๆ ที่ไม่ได้เลือกที่ไม่ได้รับอนุญาต ลำดับการใช้กุญแจมีความสำคัญ

ดังนั้น หากอินพุตเป็น m =1, n =1 ผลลัพธ์จะเป็น 9

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดขนาดอาร์เรย์ข้าม:10 x 10

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้โหนด len อาร์เรย์ที่เข้าชม

• ถ้าเลนเท่ากับ 0 แล้ว −

  • กลับ 1

• เยี่ยมชม[โหนด] :=จริง

• ยกเลิก :=0

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=9 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • หาก visit[i] เป็นเท็จ และ (skip[node, i] เหมือนกับ 0 หรือ visit[skip[node, 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 เมื่อฉัน <=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