Trong bài viết này, chúng ta sẽ cùng khám phá một bài toán thú vị mang tên “Tìm đường nhảy của chú ếch xanh” – một bài toán mô phỏng hành trình vượt chướng ngại vật để tìm đến bạn của chú ếch trong một dãy cọc gỗ. Với những điều kiện ràng buộc như bước nhảy cố định và vật cản không thể vượt qua, bài toán đòi hỏi người giải phải áp dụng các kỹ thuật xử lý mảng, thuật toán duyệt và kiểm tra khả năng tiếp cận đích.
Bài viết sẽ hướng dẫn bạn:
- ✅ Hiểu rõ yêu cầu và tư duy giải bài toán.
- ✅ Cài đặt thuật toán một cách tối ưu bằng cả Python và C++.
- ✅ Vận dụng kiến thức duyệt BFS để giải quyết các bài toán tìm đường hiệu quả.
Nếu bạn yêu thích các bài toán về đường đi, tránh vật cản, hoặc đơn giản là muốn rèn luyện kỹ năng lập trình giải thuật, thì đây chính là nội dung dành cho bạn!
📘 Mô tả bài toán
Có n chiếc cọc gỗ được xếp thành một hàng thẳng. Chú ếch xanh bắt đầu hành trình tìm đường nhảy đến gặp chú ếch vàng – người bạn của mình đang đứng ở một cọc nào đó phía trước (hoặc phía sau).
Tuy nhiên, trên đường đi có những chướng ngại vật (các cọc gỗ bị chặn) khiến chú ếch không thể đứng lên. Ở mỗi bước nhảy, chú ếch xanh có thể nhảy k cọc sang trái hoặc sang phải.
👉 Nhiệm vụ của bạn là xác định xem chú ếch xanh có thể tới được chỗ chú ếch vàng hay không.
🧠 Thuật toán
Ta cần xác định xem liệu từ vị trí ban đầu của chú ếch xanh, có thể đi đến vị trí của chú ếch vàng với bước nhảy ±k và không bị cản trở bởi chướng ngại vật (‘X’) hay không.
🚀 Ý tưởng chính:
- Sử dụng BFS (duyệt theo chiều rộng) để tìm đường đi hợp lệ từ vị trí bắt đầu.
- Tại mỗi bước, từ vị trí hiện tại, ếch có thể nhảy tới vị trí i ± k nếu vị trí đó không bị chặn và chưa thăm.
- Nếu BFS tìm tới vị trí chú ếch vàng, trả về “YES”, ngược lại là “NO”.
⏱️ Độ phức tạp:
- Thời gian: O(n), do mỗi cọc chỉ được xét 1 lần trong BFS.
- Bộ nhớ: O(n) cho mảng visited và hàng đợi.
🐍 Cài đặt bằng Python
from collections import deque
def find_path(n, k, a):
visited = [False] * n
# Tìm vị trí của ếch xanh và ếch vàng
start = a.index('S')
goal = a.index('G')
queue = deque()
queue.append(start)
visited[start] = True
while queue:
current = queue.popleft()
for step in [-k, k]:
next_pos = current + step
if 0 <= next_pos < n and not visited[next_pos] and a[next_pos] != 'X':
if next_pos == goal:
return "YES"
visited[next_pos] = True
queue.append(next_pos)
return "NO"
# Example usage
n, k = map(int, input().split())
a = list(input().strip())
print(find_path(n, k, a))
💻 Cài đặt bằng C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
string find_path(int n, int k, vector<char> &a) {
vector<bool> visited(n, false);
int start = -1, goal = -1;
// Tìm vị trí của ếch xanh và ếch vàng
for (int i = 0; i < n; i++) {
if (a[i] == 'S') start = i;
if (a[i] == 'G') goal = i;
}
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int current = q.front(); q.pop();
for (int step : {-k, k}) {
int next_pos = current + step;
if (next_pos >= 0 && next_pos < n && !visited[next_pos] && a[next_pos] != 'X') {
if (next_pos == goal)
return "YES";
visited[next_pos] = true;
q.push(next_pos);
}
}
}
return "NO";
}
int main() {
int n, k;
cin >> n >> k;
vector<char> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
cout << find_path(n, k, a) << endl;
return 0;
}
🏁 Kết luận
Bài toán tìm đường đi của chú ếch là một ứng dụng đơn giản của duyệt theo chiều rộng (BFS), cực kỳ phù hợp trong môi trường có các bước đi cố định và cần tránh vật cản. Độ phức tạp thấp nên có thể xử lý tốt với n gần 1 triệu.
