สมมติว่ามีหน้าจอล็อกแบบ Android 3x3 และจำนวนเต็มสองตัว m และ n ค่าของ m และ n อยู่ในช่วง 1 ≤ m ≤ n ≤ 9 เราต้องนับจำนวนรูปแบบปลดล็อกทั้งหมดของหน้าจอล็อก Android ซึ่งประกอบด้วยกุญแจขั้นต่ำ m ตัวและสูงสุด n ตัว
กฎคือ แต่ละรูปแบบต้องเชื่อมกุญแจอย่างน้อย m ตัวและสูงสุด n ตัว กุญแจทั้งหมดต้องไม่ซ้ำกัน หากมีเส้นเชื่อมกุญแจสองตัวติดกันในรูปแบบผ่านกุญแจอื่นๆ กุญแจอื่นๆ นั้นต้องถูกเลือกในรูปแบบก่อนหน้านี้ การกระโดดข้ามกุญแจที่ยังไม่ได้เลือกไม่ได้ ลำดับของกุญแจที่ใช้มีความสำคัญ
เช่น ถ้าอินพุทเป็น m = 1, n = 1 ผลลัพธ์จะเป็น 9
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดอาร์เรย์ skip ขนาด 10 x 10
กำหนดฟังก์ชัน dfs() รับ node, len, อาร์เรย์ visited
ถ้า len เท่ากับ 0 แล้ว −
คืนค่า 1
visited[node] := true
ret := 0
ลูป i := 1 ถึง 9 ทำ −
ถ้า visited[i] เป็น false และ (skip[node][i] เป็น 0 หรือ visited[skip[node][i]] ไม่เป็นศูนย์) แล้ว −
ret := ret + dfs(i, len - 1, visited)
visited[node] := false
คืนค่า ret
จากเมธอดหลักทำดังนี้ −
เติม skip ด้วย 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] := skip[9][1] := 5
กำหนดอาร์เรย์ visited ขนาด 10
ret := 0
ลูป i := m ถึง n ทำ −
ret := ret + (dfs(1, i - 1, visited))
ret := ret + (dfs(2, i - 1, visited))
ret := ret + dfs(5, i - 1, visited)
คืนค่า 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
