Giải thuật:
Dùng DFS hoặc BFS, sử dụng giải thuật DFS hoặc BFS tại 2 điểm bất kì sau đó DFS hoăc BFS tại điểm xa nhất của lần gọi hàm đầu tiên.
Bài này mình ngại cài Queue các bạn tham khảo Queue ví dụ trước.
Cho một mê cung được mô tả bởi "#" là đá và "." là ô trống. Hãy tìm khoảng cách xa nhất giữa 2 ô trống.
Giải thuật: Dùng DFS hoặc BFS, sử dụng giải thuật DFS hoặc BFS tại 2 điểm bất kì sau đó DFS hoăc BFS tại điểm xa nhất của lần gọi hàm đầu tiên. Bài này mình ngại cài Queue các bạn tham khảo Queue ví dụ trước. Đàn mèo đang được thả rông trong thành phố, người ta chia thành phố thành các hình vuông nhỏ và biết rằng khi đi qua hình vuông đó con mèo sẽ đi tiếp một trong 4 hướng đông, tây, nam, bắc. Hãy in ra số lượng cạm bẫy ít nhất để bắt toàn bộ số mèo.
Giải thuật: Dùng BFS tại từng ô hãy thêm vào Queue những ô sau: - Giả sử đang tại ô i.j sẽ có 4 ô xung quanh là (i+1,j), (i-1, j), (i, j+1), (i, j-1), kiểm tra 4 ô này xem ô tiếp theo của nó có phải là ô i,j hay k? nếu có hãy đánh dấu đã visit và thêm vào Queue. - Tại ô i,j ta sẽ thêm ô tiếp theo của ô i,j vào Queue. ví dụ nếu đang ở ô i,j và i,j có giá trị 'S' (Hướng nam) thì hãy thêm ô tiếp theo là i+1, j vào Queue. Chú ý: Chỉ thêm những ô chưa được visit. Cho 1 thang máy với f là số lượng tầng của thang máy, s là tầng bắt đầu, g là tầng đích, u là số tầng mà thang đi khi nhấn nút "Up", d là số tầng mà thang đi khi ấn nút "Down".
Hãy in ra số lần bấm ít nhất nút "Up" hoặc "Down" để đi từ tầng s đến tầng g. Dùng BFS, tại tầng bắt đầu thêm 2 tầng tương ứng với nút up và down vào queue, tiếp tục làm vậy đến khi Queue rỗng, dùng mảng visited để đánh dấu và lưu trữ số lần bấm nút. Cho một mê cung, mê cung được làm bởi các cell và được kết nối với nhau bằng các đường 1 chiều. Người ta nhốt những con chuột vào trong mỗi cell và được đào tạo. Nhiệm vụ của bạn là in ra số lượng chuột thoát ra khỏi mê cùng trong thời gian T.
Giải thuật: Bài này là bài tìm đường đi ngắn nhất từ các cell đến lối ra. Các bạn có thể cài đặt BFS tại vị trí cổng thoát ra và đảo chiều đường đi để tìm thời gian tối thiểu đi từ lối ra đến các cell. Đến đây các bạn sẽ nghĩ rằng làm sao để cài đặt Dijsktra bằng BFS. Cũng giống như Dijisktra các bạn cũng define 1 mảng khoảng cách ngắn nhất từ đỉnh ban đầu đến các đỉnh còn lại là vô cùng Sau đó thay vì điều kiện của BFS bình thường là nếu chưa thăm thì đánh dấu đã thăm và không cho vào Queue nữa, thì BFS bằng Dijsktra sẽ luôn luôn kiểm tra các cell đã thăm, nếu tồn tại một khoảng cách tối ưu hơn sẽ cập nhật lại nó. Về cơ bản cài Dijsktra bằng BFS sẽ lâu hơn là cài thẳng Dijsktra vì vậy người ta có một khái niêm về hàng đợi ưu tiên (Priority Queue) để tăng tốc thuật toán này. Nếu muốn tìm hiểu search Wiki :D Bài toán cho bàn cờ với kích thước 8x8 hãy tìm số nước đi tối thiểu để con mã có thể ăn quân còn lại, sao cho số bước đi ít nhất.
Giải thuật: Dùng BFS để tìm ra số bước đi ít nhất để con mã gặp được ô mà nó có thể ăn được con còn lại. Để dùng được BFS các bạn bắt buộc phải cài đặt Queue, Bên dưới mình mô tả một Queue vòng. Đề bài này hơi khó hiểu chút, cho một mạng gồm n router, tính khoảng thời gian time out để gửi lại gói tin khi xảy ra lỗi. Khoảng thời gian này là khoảng thời gian tối thiểu khi chọn 1 router trong mạng làm router trung tâm mà gói tin vẫn có thể đến tất cả các router còn lại. Giải thích : Test 2: Chọn 2 làm router trung tâm thì khoảng thời gian cần thiết sẽ là 1.
Test 3 : Chọn 1 làm router trung tâm khoảng thời gian cần thiết là 2. Giải thuật : Hãy liên tưởng đến bài toán tìm đường dài nhất trong đồ thị thì bài toán này sẽ là tìm số lượng điểm nhiều nhất giữa 2 router bất kì. Vẫn DFS 2 lần, lần 1 tại điểm bất kì và lần 2 tại điểm dài nhất đã tìm được ở lần 1. Thời gian cần thiết sẽ là tổng số node lớn nhất giữa 2 node + 1 chia 2. Trong một thí nghiệm giao phối giữa loài bọ, người ta đánh số chúng và cho chúng giao phối với nhau. Hãy kiểm tra xem có tồn tại con đồng tính trong những con được kiểm tra hay không? Code Editor
Bài này yêu cầu kiểm tra cây cho bởi input có phải là cây hay không. 1 đồ thị là cây khi có số đỉnh bằng số cạnh cộng thêm một, liên thông và không có chu trình. Solution
Cho n thị trấn và cho khoảng cách giữa 2 thị trấn. Hãy tìm ra con đường dài nhất giữa 2 thị trấn. Code Editor
Con đường dài nhất là 3 - 2 - 6 - 4 tương ứng với khoảng cách là 4 + 2 + 6 = 12
Giải thuật : DFS từ một thị trấn bất kì để tìm ra thị trấn xa nhất, sau đó DFS tại thị trấn xa nhất để tìm ra con đường dài nhất. Chú ý : Bài này input lớn nên các bạn có thể dùng vector để lưu trữ, yên tâm đề advanced của ss không bao giờ bắt cái linklist.
Trên bàn cờ người ta đặt một số lượng quân hậu, quân mã, quân tốt. Bạn hãy đếm số lượng các ô an toàn trên bàn cờ mà không bị ăn bởi quân mã và quân hậu.
Chú ý: quân tốt chỉ để chắn chứ k ăn bất kì các quân khác. Đầu vào Dòng đầu chứa kích thước ma trận là số hàng và số cột k r1 c1 r2 c2 · · · rk ck k là số lượng quân cờ, r1 c1 tương ứng là các giá trị tọa độ, biểu thị tọa độ lần lượt của các quân hậu, mã và tốt. Giá trị 0 0 thể hiện sự kết thúc của đầu vào. Đầu ra in ra số lượng các ô an toàn.
Ví dụ
Hướng dẫn giải:
Bài này chỉ việc kiểm tra 8 vị trí 1 quân mã có thể ăn tương ứng với các tọa độ. (-2, -1), (-2, 1), (2, -1), (2, 1)... và 8 hướng con hậu có thể ăn trên, dưới, trái, phải, 4 đường chéo, khác với con mã con hậu sẽ ăn từng ô 1 và cập nhật vị trí ô nó đã ăn đến khi ra ngoài bàn cờ. |
Thời Gian
December 2021
Chủ ĐỀ
All
|