Đề bài
Cho hai chuỗi str1 và str2, cả hai đều chứa ký tự 'a' và 'b'. Cả hai chuỗi có độ dài bằng nhau. Có một ký tự '_' (khoảng trống) trong cả hai chuỗi. Nhiệm vụ là chuyển đổi chuỗi đầu tiên thành chuỗi thứ hai bằng cách thực hiện số lượng phép toán sau đây tối thiểu:
- Nếu '_' ở vị trí i thì '_' có thể hoán đổi với ký tự ở vị trí i+1 hoặc i-1
- Nếu các ký tự ở vị trí i+1 và i+2 khác nhau thì '_' có thể hoán đổi với ký tự ở vị trí i+1 hoặc i+2
- Tương tự, nếu các ký tự ở vị trí i-1 và i-2 khác nhau thì '_' có thể hoán đổi với ký tự ở vị trí i-1 hoặc i-2
Nếu str1 = "aba_a" và str2 = "_baaa" thì cần 2 lần di chuyển để biến str1 thành str2:
1. str1 = "ab_aa" (Hoán đổi str1[2] với str1[3]) 2. str2 = "_baaa" (Hoán đổi str1[0] với str1[2])
Thuật toán
1. Áp dụng Breadth First Search đơn giản trên chuỗi và một phần tử của hàng đợi dùng cho BFS sẽ chứa cặp str, pos trong đó pos là vị trí của '_' trong chuỗi str. 2. Cũng duy trì một map tên là 'vis' sẽ lưu chuỗi làm khóa và số lần di chuyển tối thiểu để đến chuỗi đó làm giá trị. 3. Với mỗi chuỗi str từ hàng đợi, tạo chuỗi mới tmp dựa trên bốn điều kiện cho trước và cập nhật map vis như vis[tmp] = vis[str] + 1. 4. Lặp lại các bước cho đến khi hàng đợi rỗng hoặc chuỗi yêu cầu được tạo ra tức là tmp == B 5. Nếu chuỗi yêu cầu được tạo, trả về vis[str] + 1 là số phép toán tối thiểu để đổi A thành B.
Ví dụ
#include <iostream> #include <string> #include <unordered_map> #include <queue> using namespace std; int transformString(string str, string f){ unordered_map<string, int> vis; int n; n = str.length(); int pos = 0; for (int i = 0; i < str.length(); i++) { if (str[i] == '_') { pos = i; break; } } queue<pair<string, int> > q; q.push({ str, pos }); vis[str] = 0; while (!q.empty()) { string ss = q.front().first; int pp = q.front().second; int dist = vis[ss]; q.pop(); if (pp > 0) { swap(ss[pp], ss[pp - 1]); if (!vis.count(ss)) { if (ss == f) { return dist + 1; break; } vis[ss] = dist + 1; q.push({ ss, pp - 1 }); } swap(ss[pp], ss[pp - 1]); } if (pp < n - 1) { swap(ss[pp], ss[pp + 1]); if (!vis.count(ss)) { if (ss == f) { return dist + 1; break; } vis[ss] = dist + 1; q.push({ ss, pp + 1 }); } swap(ss[pp], ss[pp + 1]); } if (pp > 1 && ss[pp - 1] != ss[pp - 2]) { swap(ss[pp], ss[pp - 2]); if (!vis.count(ss)) { if (ss == f) { return dist + 1; break; } vis[ss] = dist + 1; q.push({ ss, pp - 2 }); } swap(ss[pp], ss[pp - 2]); } if (pp < n - 2 && ss[pp + 1] != ss[pp + 2]) { swap(ss[pp], ss[pp + 2]); if (!vis.count(ss)) { if (ss == f) { return dist + 1; break; } vis[ss] = dist + 1; q.push({ ss, pp + 2 }); } swap(ss[pp], ss[pp + 2]); } } return 0; } int main(){ string str1 = "aba_a"; string str2 = "_baaa"; cout << "Minimum required moves: " << transformString(str1, str2) << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum required moves: 2