tag: dijkstra, implementation, data structure.

Nhận xét: ngoại trừ ô ~(0, 0)~, con gà trống chỉ có thể đứng trên một ô kề với vật cản. Vì vậy, chỉ tồn tại tối đa ~4 * N~ tọa độ mà con gà trống có thể đến, và ở mỗi điểm con gà trống chỉ có thể đi đến tối đa ~3~ địa điểm khác.

Với số đỉnh và số cạnh thấp như thế, ta có thể mô hình hóa bài toán thành một bài toán đồ thị. Đầu tiên ta sẽ xây dựng đồ thị từ bảng trên, rồi sử dụng thuật toán tìm đường đi ngắn nhất Dijkstra. Nếu cạnh nối giữa hai điểm ~(u, v)~ → ~(i, j)~ đi qua chìa khóa ~t~ có tọa độ ~(x_t, y_t)~, thì ta sẽ cập nhật chi phí thấp nhất để lấy được chìa khóa là chi phí thấp nhât để đi đến tọa độ ~(i, j)~ mà phải đi qua cạnh ~(u, v)~ → ~(i, j)~.

Như vậy, vấn đề của chúng ta là xây dựng đồ thị và cập nhật kết quả như thế nào cho nhanh.

Subtask 1:

Ta chỉ cần loang trên bảng để giải quyết phần xây dựng đồ thị. Với mỗi chìa khóa, ta duyệt qua tất cả các cạnh ~(u, v)~ → ~(i, j)~, kiểm tra xem cạnh có đi qua chìa khóa không, và cập nhật kết quả.

Độ phức tạp: ~O(n * 200)~ để xây dựng đồ thị, và ~O(n * q)~ để cập nhật kết quả.

Subtask 2:

Về phần cập nhật kết quả, ta làm tương tự như Subtask ~1~. Ta có thể tăng tốc cho phần xây dựng đồ thị bằng cách duy trì mảng~X_i~, lưu trữ những điểm ở hàng ~i~ và mảng ~Y_j~, lưu trữ những điểm ở cột ~j~. Sau đó, ta chỉ cần sử dụng chặt nhị phân để tìm những vật cản cùng hàng gần nhất với điểm ~(u, v)~ về bên trái và bên phải, và làm tương tự với cột.

Độ phức tạp: ~O(n * log_2(n))~ để xây dựng đồ thị, và ~O(n * q)~ để cập nhật kết quả.

Subtask 3:

Ta cần tăng tốc độ ở phần cập nhật kết quả. Về phần kết quả, bài toán của chúng ta về cơ bản là: cho ~n~ đoạn thẳng song song với trục tọa độ, mỗi đoạn thẳng có trọng số và ~q~ điểm, với mỗi điểm tìm đoạn thẳng có trọng số nhỏ nhất và đi qua điểm đó.

Vì mỗi đoạn thẳng song song với trục tọa độ, nên ta chỉ cần lặp qua từng hàng, từng cột. Với mỗi hàng/cột, ta sử dụng CTDL Segment Tree để cập nhật kết quả.

Độ phức tạp: ~O(n * log_2(n))~ để xây dựng đồ thị, và ~O((n + q) * log_2(n))~ để cập nhật kết quả.