Hướng dẫn giải của Lập trình cho Rô-bốt
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, bvquoc
, ,
Hiểu bài toán
Xác định số lượng thao tác chỉnh sửa (xóa hoặc chèn lệnh) ít nhất để biến dãy lệnh ban đầu thành một dãy lệnh mới đưa rô-bốt từ 'S' đến 'G'. Rô-bốt bỏ qua lệnh nếu đi ra ngoài bảng hoặc vào chướng ngại vật, và dừng lại khi đến 'G'. Bài toán có thể được nhìn nhận như tìm đường đi ngắn nhất (thao tác chỉnh sửa) trên một đồ thị các trạng thái (vị trí rô-bốt, chỉ số lệnh đã duyệt).
Các cách tiếp cận
Cách BFS 0-1 (Đồ thị trạng thái)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, m;
vector<string> grid;
string s;
int sr, sc, gr, gc;
struct State {
int r, c, idx;
};
int dist[55][55][55]; //[r][c][idx]
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
grid.resize(n);
for (int i = 0; i < n; ++i) {
cin >> grid[i];
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 'S') { sr = i; sc = j; }
if (grid[i][j] == 'G') { gr = i; gc = j; }
}
}
cin >> s;
int L = s.size();
// Initialize distances
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
for(int k=0; k<=L; ++k)
dist[i][j][k] = INF;
deque<State> dq;
dist[sr][sc][0] = 0;
dq.push_back({sr, sc, 0});
while(!dq.empty()) {
State u = dq.front(); dq.pop_front();
int d = dist[u.r][u.c][u.idx];
// Goal check
if (u.r == gr && u.c == gc) {
cout << d << endl;
return 0;
}
// Option 1: Delete current command (Cost 1)
// Move to next command in sequence
if (u.idx < L) {
if (d + 1 < dist[u.r][u.c][u.idx + 1]) {
dist[u.r][u.c][u.idx + 1] = d + 1;
dq.push_back({u.r, u.c, u.idx + 1}); // Cost 1, push back or front depending on 0-1 logic (standard 0-1 BFS pushes front for 0, back for 1)
// Wait, standard deque: push_front for cost 0, push_back for cost 1
}
}
// Option 2: Use current command (Cost 0)
// Try to execute s[u.idx]
if (u.idx < L) {
char cmd = s[u.idx];
int nr = u.r, nc = u.c;
if (cmd == 'U' && u.r > 0 && grid[u.r-1][u.c] != '#') nr--;
else if (cmd == 'D' && u.r < n-1 && grid[u.r+1][u.c] != '#') nr++;
else if (cmd == 'L' && u.c > 0 && grid[u.r][u.c-1] != '#') nc--;
else if (cmd == 'R' && u.c < m-1 && grid[u.r][u.c+1] != '#') nc++;
// If invalid move, nr, nc stay same (skip command)
// Push front because cost is 0 (we keep the command)
if (d < dist[nr][nc][u.idx + 1]) {
dist[nr][nc][u.idx + 1] = d;
dq.push_front({nr, nc, u.idx + 1});
}
}
}
// Should not reach here given problem constraints
return 0;
}
- Time Complexity: O(N * M * L)
- Space Complexity: O(N * M * L)
Sử dụng thuật toán BFS trên đồ thị các trạng thái (vị trí rô-bốt, chỉ số lệnh đang xem). Mỗi trạng thái là một đỉnh. Có 2 loại cạnh:
- Giữ lại lệnh hiện tại (tiếp tục thực hiện lệnh): Chi phí 0. Nếu lệnh hợp lệ thì di chuyển, nếu không thì ở yên tại chỗ. Luôn tăng chỉ số lệnh lên 1.
- Xóa lệnh hiện tại: Chi phí 1. Ở yên tại chỗ, tăng chỉ số lệnh lên 1. Do chi phí cạnh là 0 hoặc 1, ta dùng deque (0-1 BFS) để tìm đường đi ngắn nhất (tổng chi phí chỉnh sửa nhỏ nhất) từ (S, 0) đến bất kỳ trạng thái nào tại vị trí G.
Cách BFS 0-1 (Cải tiến)
// Tương tự Approach 1
- Time Complexity: O(N * M * L)
- Space Complexity: O(N * M * L)
Đây là cách tiếp cận tối ưu nhất cho bài toán này. Nó kết hợp BFS với kỹ thuật 0-1 Weight để xử lý chi phí xóa lệnh (1) và giữ lệnh (0). Việc sử dụng deque đảm bảo độ phức tạp tuyến tính với số lượng trạng thái.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * M * L) | O(N * M * L) | BFS 0-1 (Đồ thị trạng thái) |
| 2 | O(N * M * L) | O(N * M * L) | BFS 0-1 (Cải tiến) |
Bài học kinh nghiệm
- Bài toán có thể biến đổi thành bài tìm đường đi ngắn nhất trên đồ thị có trọng số 0 và 1.
- Trạng thái được định nghĩa bởi tọa độ (r, c) và chỉ số lệnh đã xử lý (idx).
- Việc 'bỏ qua' lệnh do chướng ngại vật hoặc biên là một hành động mặc định khi thực thi lệnh, không tốn chi phí chỉnh sửa.
Lỗi thường gặp
- Lầm tưởng rằng phải xóa các lệnh bị bỏ qua do chướng ngại vật. Thực tế, chỉ cần giữ nguyên lệnh trong dãy, rô-bốt sẽ tự động bỏ qua.
- Quên trường hợp rô-bốt đến đích giữa chừng chuỗi lệnh (khi đó không cần xử lý phần còn lại của chuỗi).
Bình luận