NỘI DUNG
Bài toán Giải cứu Hermione
Trong lâu đài Dungeon có một tòa nhà được sắp xếp theo dạng lưới chữ nhật M × N, các hàng được đánh số thứ tự từ 1 đến M theo hướng từ trên xuống dưới, các cột được đánh số thứ tự từ 1 đến N theo hướng từ trái sang phải; mỗi ô (i,j) được xem là một căn phòng.
Do lòng thù hận của mình, ác quỷ Lucius Malfoy đã giam cầm Hermione tại một phòng trong tòa nhà. Harry Potter đang trên đường giải cứu Hermione. Harry Potter chỉ có thể vào tòa nhà bằng con đường duy nhất dẫn đến phòng ở ô (1,1). Mỗi phòng của tòa nhà có một số vệ sĩ và Harry phải mất một khoảng thời gian để đánh bại các tên vệ sĩ của phòng đó. Thời gian đánh bại các vệ sĩ thay đổi theo từng phòng. Ngay sau khi đánh bại tất cả các vệ sĩ trong phòng, Harry có thể di chuyển đến phòng bất kỳ chung cạnh bằng cách đi sang trái, phải, lên hoặc xuống nếu căn phòng đó thuộc tòa nhà (không thể di chuyển theo đường chéo).
Ác quỷ Lucius Malfoy biết rằng Harry Potter đang đi đến tòa nhà để giải cứu Hermione, nên ngay khi Harry vừa đến cửa phòng (1,1), hắn đã đặt một quả bom hẹn giờ sẽ giết Hermione sau T giây. Bạn sẽ nhận được vị trí phòng giam Hermione, thời gian để bom nổ và thời gian Harry cần để đánh bại các vệ sĩ trong mỗi phòng.
Yêu cầu: Nhiệm vụ của bạn là xác định xem liệu Harry có thể tiếp cận Hermione hay không và cứu cô ta bằng cách dẹp bỏ bom trước khi hết T giây.
Quy ước: Ngay sau khi Harry đánh bại các vệ sĩ tại phòng giam Hermione thì xem như Harry tiếp cận được Hermione. Thời gian Harry dẹp bỏ bom không đáng kể (xem như bằng 0). Như vậy, nếu tổng thời gian mà Harry đánh bại tất cả các vệ sĩ ở tất cả các phòng trên đường đi từ phòng (1,1) đến phòng giam Hermione mà nhỏ hơn hoặc bằng T thì xem như Hermione được cứu.
Dữ liệu: Vào từ file văn bản GIAICUU.INP gồm nhiều dòng:
- Dòng đầu tiên chứa số nguyên K (1 ≤ K ≤ 20) là số lượng bộ test (test cases).
- Sau đó là K nhóm dòng, mỗi nhóm gồm nhiều dòng:
- Dòng 1: chứa hai số nguyên M, N (1≤ N, M ≤100);
- Trong M dòng tiếp theo, mỗi dòng chứa N số, số thứ j trên dòng thứ i là số nguyên dương Cij (Cij ≤ 1000) là thời gian để tiêu diệt các vệ sĩ ở phòng (i,j);
- Dòng cuối nhóm: chứa ba số nguyên a, b, T (1 ≤ a ≤ M, 1 ≤ b ≤ N, 1 ≤ T ≤ 106); với (a,b) là vị trí phòng giam Hermione, T là thời gian hẹn nổ của quả bom.
Các số trên cùng dòng cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản GIAICUU.OUT; ứng với test case mà Harry không thể giải cứu được Hermione thì chỉ ghi là ‘NO’; còn với test case mà Harry giải cứu được Hermione thì ghi hai dòng: dòng đầu ghi ‘YES’, dòng tiếp theo sau đó ghi thời gian còn dư lớn nhất mà Harry có thể có sau khi Harry giải cứu Hermione.
Ví dụ:
|
GIAICUU.INP |
GIAICUU.OUT |
|
2 4 3 2 3 2 2 5 1 5 3 1 3 1 1 4 2 15 2 2 1 2 1 1 2 2 2 |
YES 4 NO |
Giải thích test case 1: Thời gian ngắn nhất để Harry giải cứu Hermione là: 2+3+2+1+1+1+1= 11 Thời gian hẹn bom nổ là: 15 Thời gian dư lớn nhất của Harry là: 15-11= 4.
Hiểu rõ hơn Bài toán Giải cứu Hermione
“Giải cứu Hermione” (tiếng Anh: “Saving Hermione”) là một bài toán trong lĩnh vực tin học giải thuật. Bài toán được đặt tên theo nhân vật Hermione Granger trong bộ tiểu thuyết nổi tiếng “Harry Potter” của tác giả J.K. Rowling.
Bài toán được mô tả như sau: Harry và Ron đang cố gắng giải cứu Hermione, nhưng họ bị mắc kẹt trong mê cung. Mê cung được chia thành một lưới các ô vuông kích thước MxN, trong đó ô trên cùng bên trái là (1,1) và ô dưới cùng bên phải là (M,N). Mỗi ô có một giá trị nguyên dương đại diện cho độ khó để đi qua ô đó. Hai ô liền kề có thể được di chuyển qua nếu giá trị của ô đó không vượt quá một giá trị nguyên dương T.
Harry và Ron đang ở vị trí (1,1) và cần giải cứu Hermione ở vị trí (A,B). Họ chỉ có thể di chuyển theo đường đi trên lưới, tức là di chuyển từ ô (i,j) đến ô (i+1,j), (i,j+1), (i-1,j), hoặc (i,j-1). Hãy giúp Harry và Ron tìm đường đi từ (1,1) đến (A,B) sao cho độ khó của đường đi là nhỏ nhất và không vượt quá giá trị T. Nếu không có đường đi nào từ (1,1) đến (A,B) thỏa mãn điều kiện, in ra “NO”.
Bài toán này có thể được giải quyết bằng nhiều phương pháp, ví dụ như thuật toán Dijkstra hoặc thuật toán BFS (Breath First Search).
Cài đặt Bài toán Giải cứu Hermione
Để giải quyết bài toán này, ta có thể sử dụng thuật toán tìm đường đi ngắn nhất trong đồ thị vô hướng có trọng số. Đầu tiên, ta tạo đồ thị vô hướng với các đỉnh là các căn phòng trong lâu đài Dungeon và các cạnh nối giữa các căn phòng. Giữa hai căn phòng có cạnh nối nếu chúng nằm cạnh nhau (không đi theo đường chéo) và có thể di chuyển từ một căn phòng sang căn phòng kia bằng cách đánh bại tất cả các vệ sĩ trong căn phòng đang đứng.
Sau khi tạo đồ thị, ta có thể áp dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ căn phòng (1,1) đến căn phòng giam Hermione. Nếu thời gian đi hết đường đi này (bao gồm cả thời gian đánh bại các vệ sĩ) nhỏ hơn hoặc bằng thời gian hẹn nổ của quả bom, ta sẽ giải cứu được Hermione, ngược lại ta không thể giải cứu được Hermione.
Độ phức tạp của thuật toán là O(MN log MN), do ta sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất. Với M, N tối đa là 100 thì thuật toán này hoàn toàn có thể chạy được trong thời gian chấp nhận được.
Mã giả của thuật toán
Đọc số lượng bộ test K
Lặp lại K lần:
Đọc vào số M, N
Khởi tạo đồ thị với M x N đỉnh và các cạnh nối giữa các đỉnh tương ứng
Đọc ma trận thời gian để đánh bại vệ sĩ cho từng căn phòng
Đọc vị trí phòng giam Hermione và thời gian hẹn nổ của quả bom
Áp dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ căn phòng (1,1) đến căn phòng giam Hermione
Nếu thời gian đi hết đường đi này nhỏ hơn hoặc bằng thời gian hẹn nổ của quả bom, in ra "YES" và thời gian đi hết đường đi này
Ngược lại, in ra "NO"
Cài đặt bài toán Giải cứu Hermione với Python
from queue import Queue
# Đọc file input và ghi file output
with open("GIAICUU.INP", "r") as f_in, open("GIAICUU.OUT", "w") as f_out:
t = int(f_in.readline())
for _ in range(t):
m, n = map(int, f_in.readline().split())
c = []
for i in range(m):
row = list(map(int, f_in.readline().split()))
c.append(row)
a, b, T = map(int, f_in.readline().split())
# tính độ dài từ (1,1) đến (a,b) thông qua BFS
d = [[-1 for _ in range(n)] for _ in range(m)]
q = Queue()
q.put((0, 0))
d[0][0] = 0
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
while not q.empty():
x, y = q.get()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < m and 0 <= ny < n and d[nx][ny] == -1 and c[nx][ny] <= T - d[x][y]:
d[nx][ny] = d[x][y] + c[nx][ny]
q.put((nx, ny))
if d[a-1][b-1] == -1:
f_out.write("NO\n")
else:
f_out.write("YES\n" + str(d[a-1][b-1]) + "\n")
Cài đặt bài toán Giải cứu Hermione với C++
#include<bits/stdc++.h>
using namespace std;
int main() {
freopen("GIAICUU.INP","r",stdin);
freopen("GIAICUU.OUT","w",stdout);
int t;
cin >> t;
while (t--) {
int m, n;
cin >> m >> n;
int a, b, T;
vector<vector<int>> c(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> c[i][j];
}
}
cin >> a >> b >> T;
// tính độ dài từ (1,1) đến (a,b) thông qua BFS
vector<vector<int>> d(m, vector<int>(n, -1));
queue<pair<int, int>> q;
q.push({0, 0});
d[0][0] = 0;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && d[nx][ny] == -1 && c[nx][ny] <= T - d[x][y]) {
d[nx][ny] = d[x][y] + c[nx][ny];
q.push({nx, ny});
}
}
}
if (d[a - 1][b - 1] == -1) {
cout << "NO\n";
} else {
cout << "YES\n" << d[a - 1][b - 1] << "\n";
}
}
return 0;
}
Tham khảo thêm việc sử dụng thuật toán dijkstra
import heapq
def dijkstra(graph, start):
n = len(graph)
dist = [float('inf')] * n
visited = [False] * n
dist[start] = 0
pq = [(0, start)]
while pq:
(d, u) = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
def solve():
m, n = map(int, input().split())
graph = [[] for _ in range(m * n)]
for i in range(m):
row = list(map(int, input().split()))
for j in range(n):
if i > 0:
graph[n * i + j].append((n * (i - 1) + j, row[j]))
if j > 0:
graph[n * i + j].append((n * i + j - 1, row[j - 1]))
if i < m - 1:
graph[n * i + j].append((n * (i + 1) + j, row[j]))
if j < n - 1:
graph[n * i + j].append((n * i + j + 1, row[j + 1]))
a, b, T = map(int, input().split())
start = 0
end = n * (a - 1) + (b - 1)
dist = dijkstra(graph, start)
if dist[end] <= T:
print("YES")
print(T - dist[end])
else:
print("NO")
k = int(input())
for _ in range(k):
solve()
Tham khảo thêm một số bài toán có tính chất tương tự
Bài toán Giải cứu Hermione là một dạng bài toán truy vấn đường đi trên đồ thị. Một số bài toán có tính chất tương tự như Bài toán Giải cứu Hermione là:
-
Bài toán đường đi ngắn nhất (Shortest Path Problem): Tìm đường đi ngắn nhất từ một đỉnh đến một đỉnh khác trên đồ thị, thường được giải bằng thuật toán Dijkstra hoặc Bellman-Ford.
-
Bài toán đường đi dài nhất (Longest Path Problem): Tìm đường đi dài nhất từ một đỉnh đến một đỉnh khác trên đồ thị.
-
Bài toán đường đi Euler (Euler Path Problem): Tìm đường đi qua tất cả các cạnh trên đồ thị mà mỗi cạnh chỉ đi qua một lần.
-
Bài toán đường đi Hamilton (Hamiltonian Path Problem): Tìm đường đi qua tất cả các đỉnh trên đồ thị mà mỗi đỉnh chỉ đi qua một lần.
-
Bài toán tìm đường đi trên đồ thị có trọng số âm (Negative Weight Cycle Problem): Tìm đường đi trên đồ thị có trọng số âm từ một đỉnh đến một đỉnh khác.
-
Bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree Problem): Tìm cây khung của một đồ thị có trọng số sao cho tổng trọng số của cây khung là nhỏ nhất, thường được giải bằng thuật toán Prim hoặc Kruskal.
-
Bài toán tìm đường đi ngắn nhất trong đồ thị có trọng số âm (Shortest Path Problem with Negative Weights): Tìm đường đi ngắn nhất từ một đỉnh đến một đỉnh khác trên đồ thị có trọng số âm.
-
Bài toán tìm chu trình Hamilton (Hamiltonian Cycle Problem): Tìm chu trình qua tất cả các đỉnh trên đồ thị mà mỗi đỉnh chỉ đi qua một lần.
-
Bài toán tìm đường đi trên đồ thị vô hướng có trọng số (Weighted Graph Path Problem): Tìm đường đi từ một đỉnh đến một đỉnh khác trên đồ thị vô hướng có trọng số.