Các mẫu mở khóa Android trong C ++

Giả sử chúng ta có màn hình khóa phím 3x3 của Android và hai số nguyên m và n, giá trị của m và n nằm trong khoảng 1 ≤ m ≤ n ≤ 9, Chúng ta phải đếm tổng số kiểu mở khóa của màn hình khóa Android, bao gồm tối thiểu m khóa và tối đa n khóa.

Quy tắc là như vậy, mỗi mẫu phải kết nối ít nhất m khóa và nhiều nhất n khóa. Tất cả các khóa phải là duy nhất. Nếu có một đường nối hai phím liên tiếp trong mẫu đi qua bất kỳ phím nào khác thì các phím khác phải được chọn trước đó trong mẫu. Nhảy qua bất kỳ phím nào không được chọn mà không được phép. Thứ tự của các khóa được sử dụng rất quan trọng.

Vì vậy, nếu đầu vào là m =1, n =1, thì đầu ra sẽ là 9

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định kích thước bỏ qua mảng:10 x 10.
Định nghĩa một hàm dfs (), hàm này sẽ lấy nút, len, một mảng được truy cập,
nếu len giống 0, thì -
- trả lại 1
đã ghé thăm [node]:=true
ret:=0
để khởi tạo i:=1, khi i <=9, hãy cập nhật (tăng i lên 1), thực hiện -
- nếu lượt truy cập [i] là sai và (bỏ qua [nút, i] giống 0 hoặc đã truy cập [bỏ qua [nút, i]] là khác), thì -
  - ret:=ret + dfs (i, len - 1, đã truy cập)
đã truy cập [node]:=false
trả lại ret
Từ phương thức chính, hãy làm như sau -
điền vào phần bỏ qua bằng 0
bỏ qua [1, 3]:=bỏ qua [3, 1]:=2
bỏ qua [1, 7]:=bỏ qua [7, 1]:=4
bỏ qua [3, 9]:=bỏ qua [9, 3]:=6
bỏ qua [7, 9]:=bỏ qua [9, 7]:=8
bỏ qua [4, 6]:=bỏ qua [6, 4]:=bỏ qua [2, 8]:=bỏ qua [8, 2]:=bỏ qua [3, 7]:=bỏ qua [7, 3]:=bỏ qua [ 1, 9]:=bỏ qua [9, 1]:=5
Xác định một mảng được truy cập có kích thước 10
ret:=0
để khởi tạo i:=m, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
- ret:=ret + (dfs (1, i - 1, đã truy cập))
- ret:=ret + (dfs (2, i - 1, đã truy cập))
- ret:=ret + dfs (5, i - 1, đã truy cập)
trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

1, 1

Các mẫu mở khóa Android trong C ++

Ví dụ

Đầu vào

Đầu ra