คำอธิบาย
กำหนดอาร์เรย์ของ N ตัวเลขที่เป็นการสลับของ N ตัวแรก ในหนึ่งการดำเนินการ สามารถกลับคำนำหน้า (prefix) ใดๆ ได้ งานคือหาจำนวนการดำเนินการน้อยที่สุดแบบนี้ เพื่อให้ตัวเลขในอาร์เรย์เรียงตามลำดับเพิ่มขึ้น
ตัวอย่าง
ถ้าอาร์เรย์คือ {1, 2, 4, 3} ต้องการขั้นตอนขั้นต่ำ 3 ขั้นตอนเพื่อเรียงอาร์เรย์ในลำดับเพิ่มขึ้น −
- กลับอาร์เรย์ทั้งหมด {3, 4, 2, 1}
- กลับสองสมาชิกแรก {4, 3, 2, 1}
- กลับอาร์เรย์ทั้งหมด {1, 2, 3, 4}
อัลกอริทึม
- เข้ารหัสตัวเลขที่กำหนดให้เป็นสตริง เรียงอาร์เรย์และเข้ารหัสเป็นสตริงปลายทาง
- ทำ BFS จากการสลับเริ่มต้น ทุกครั้งตรวจสอบการสลับทั้งหมดที่เกิดจากการกลับคำนำหน้าของการสลับปัจจุบัน
- ถ้ายังไม่ได้เยี่ยมชม ใส่เข้าในคิวพร้อมจำนวนการกลับที่ทำไปแล้ว
- เมื่อการสลับของสตริงที่เข้ารหัสตรงกับสตริงปลายทาง ให้คืนจำนวนการกลับที่ต้องใช้เพื่อไปถึงที่นี่
- นั่นคือ ทำการสลับของสตริงทั้งหมด และคืนค่าที่น้อยที่สุดเป็นคำตอบ
ตัวอย่าง
#include <iostream> #include <algorithm> #include <queue> using namespace std; int minimumPrefixReversals(int *a, int n) { string start = ""; string destination = "", t, r; for (int i = 0; i < n; i++) { start += to_string(a[i]); } sort(a, a + n); for (int i = 0; i < n; i++) { destination += to_string(a[i]); } queue<pair<string, int> > qu; pair<string, int> p; qu.push(make_pair(start, 0)); if (start == destination) { return 0; } while (!qu.empty()) { p = qu.front(); t = p.first; qu.pop(); for (int j = 2; j <= n; j++) { r = t; reverse(r.begin(), r.begin() + j); if (r == destination) { return p.second + 1; } qu.push(make_pair(r, p.second + 1)); } } } int main() { int a[] = { 1, 2, 4, 3 }; int n = sizeof(a) / sizeof(a[0]); cout << "Minimum reversal: " << minimumPrefixReversals(a, n) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้
Minimum reversal: 3
