แนวคิด
เมื่อได้รับกริดของตัวเลข ให้หาลำดับ Snake ที่ยาวที่สุดและแสดงออกมา สังเกตได้ว่าถ้ามีลำดับ Snake หลายลำดับที่มีความยาวสูงสุด ให้แสดงอันใดก็ได้หนึ่งอัน
จริงๆ แล้วลำดับ Snake ประกอบด้วยตัวเลขที่ติดกันในกริด เพื่อให้สำหรับตัวเลขแต่ละตัว ตัวเลขทางขวาหรือตัวเลขด้านล่างจะเป็น +1 หรือ -1 ของค่าของมัน ที่นี่ เช่น ถ้าเราอยู่ที่ตำแหน่ง (a, b) ในกริด เราสามารถเคลื่อนที่ไปทางขวาได้ คือ (a, b+1) ถ้าตัวเลขนั้นคือ ± 1 หรือเคลื่อนที่ลงได้ คือ (a+1, b) ถ้าตัวเลขนั้นคือ ± 1
ตัวอย่างเช่น
10, 7, 6, 3 9, 8, 7, 6 8, 4, 2, 7 2, 2, 2, 8
ในกริดข้างต้น ลำดับ Snake สูงสุดคือ: (10, 9, 8, 7, 6, 7, 8)
รูปด้านล่างแสดงเส้นทางที่เป็นไปได้ทั้งหมด −
10 7 →6 3 ↓ ↓ ↓ 9 → 8 → 7→ 6 ↓↓ 8 4 2 7 ↓ 2 2 2 8
วิธีการ
ที่นี่แนวคิดคือใช้ Dynamic Programming สำหรับแต่ละเซลล์ของเมทริกซ์ เราเก็บความยาวที่ยาวที่สุดของ Snake ที่จบในเซลล์ปัจจุบัน ความยาวของลำดับ Snake ที่ยาวที่สุดจะมีค่าสูงสุด เซลล์ที่มีค่าสูงสุดจะสอดคล้องกับปลายของ Snake สำหรับการพิมพ์ Snake เราต้องย้อนกลับจากปลายไปจนถึงหัวของ Snake สมมติ T[a][b] แทนความยาวสูงสุดของ Snake ที่จบที่เซลล์ (a, b) แล้วสำหรับเมทริกซ์ M ที่กำหนด ความสัมพันธ์ Dynamic Programming ถูกกำหนดว่า −
T[0][0] = 0 T[a][b] = max(T[a][b], T[a][b – 1] + 1) if M[a][b] = M[a][b – 1] ± 1 T[a][b] = max(T[a][b], T[a – 1][b] + 1) if M[a][b] = M[a – 1][b] ± 1
ตัวอย่างโค้ด
// โปรแกรม C++ เพื่อหาความยาวสูงสุด // ของลำดับ Snake และพิมพ์มัน #include <bits/stdc++.h> using namespace std; #define M 4 #define N 4 struct Point{ int X, Y; }; // ฟังก์ชันแสดงการหาเส้นทางลำดับ Snake สูงสุด // (a, b) สอดคล้องกับปลายของ Snake list<Point> findPath(int grid1[M][N], int mat1[M][N], int a, int b){ list<Point> path1; Point pt1 = {a, b}; path1.push_front(pt1); while (grid1[a][b] != 0){ if (a > 0 && grid1[a][b] - 1 == grid1[a - 1][b]){ pt1 = {a - 1, b}; path1.push_front(pt1); a--; } else if (b > 0 && grid1[a][b] - 1 == grid1[a][b - 1]){ pt1 = {a, b - 1}; path1.push_front(pt1); b--; } } return path1; } // ฟังก์ชันแสดงการหาลำดับ Snake สูงสุด void findSnakeSequence(int mat1[M][N]){ // ตารางแสดงการเก็บผลลัพธ์ของ subproblems int lookup1[M][N]; // ใช้เริ่มต้นด้วย 0 memset(lookup1, 0, sizeof lookup1); // ใช้เก็บความยาวสูงสุดของลำดับ Snake int max_len1 = 0; // ใช้เก็บพิกัดของปลาย Snake int max_row1 = 0; int max_col1 = 0; // ใช้เติมตารางแบบ bottom-up for (int a = 0; a < M; a++){ for (int b = 0; b < N; b++){ // ทำทุกอย่างยกเว้นเซลล์ (0, 0) if (a || b){ // มองขึ้น if (a > 0 && abs(mat1[a - 1][b] - mat1[a][b]) == 1){ lookup1[a][b] = max(lookup1[a][b], lookup1[a - 1][b] + 1); if (max_len1 < lookup1[a][b]){ max_len1 = lookup1[a][b]; max_row1 = a, max_col1 = b; } } // มองซ้าย if (b > 0 && abs(mat1[a][b - 1] - mat1[a][b]) == 1){ lookup1[a][b] = max(lookup1[a][b], lookup1[a][b - 1] + 1); if (max_len1 < lookup1[a][b]){ max_len1 = lookup1[a][b]; max_row1 = a, max_col1 = b; } } } } } cout << "Maximum length of Snake sequence is: " << max_len1 << endl; // หาเส้นทางลำดับ Snake สูงสุด list<Point> path1 = findPath(lookup1, mat1, max_row1, max_col1); cout << "Snake sequence is:"; for (auto it = path1.begin(); it != path1.end(); it++) cout << endl << mat1[it->X][it->Y] << " ("<< it->X << ", " << it->Y << ")" ;} // โค้ดหลัก int main(){ int mat1[M][N] ={{10, 7, 6, 3},{9, 8, 7, 6},{8, 4, 2, 7},{2, 2, 2, 8},}; findSnakeSequence(mat1); return 0; }เอาต์พุต
Maximum length of Snake sequence is: 6 Snake sequence is: 10 (0, 0) 9 (1, 0) 8 (1, 1) 7 (1, 2) 6 (1, 3) 7 (2, 3) 8 (3, 3)
