Cho 1 ma trận chứa 1 con robot và các vết bẩn, hãy tính số bước đi tối thiểu để con robot có thể lau hết tất cả các vết bẩn này. Giải thuật: Bài này chúng ta có 1 điểm bắt đầu và N điểm cần đi qua. - Không thể xác định điểm nào sẽ đi đầu tiên để số bước đi là lớn nhất vì vậy với N + 1 điểm. Hãy xây dựng ma trận N+1 x N+1. Với i và j thuộc N+1 điểm thì giá trị của ma trận [i][j] chính là đường đi ngắn nhất từ i đến j. - Việc tính toán đường đi ngắn nhất từ i đến j có thể thông qua thuật toán BFS. cụ thể ở đây ta sẽ tạo ra N+1 bảng BFS tương ứng với N+1 điểm này. Solution
Đề bài yêu cầu xác định ma trận sudoku dựa trên ma trận đầu vào 9x9. Với giá trị 0 là giá trị cần phải điền số phù hợp sao cho mỗi hàng, mỗi cột, mỗi hình vuông con 3x3 chỉ tồn tại duy nhất 1 số từ 1 đến 9. Nếu k thể tìm được ma trận phù hợp với đề bài in ra "No solution".
Đề 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. Bài toán :
Đi từ các đỉnh X chứa giá trị 1 nằm trên hàng 0 có giá trị 1 xuống dưới đáy sao cho đi theo các giá trị 1 , gặp ngã rẽ bắt buộc phải rẽ khi nào đến hàng cuối cùng in ra vị trí x có chiều dài đến hàng cuối cùng mà có đường đi là đường ngắn nhất. Nếu 2 vị trí có cùng giá của đường đi thì trả về vị trí cao nhất. Ví dụ tại vị trí hàng 0 cột 4 đi mất 20, và hàng 0 cột 9 đi mất 20 thì in ra output là 9 Chú ý : Input : Ma trận đầu vào là 100x100, chỉ có 2 giá trị là 0, 1. Output : In ra cột có đường đi ngắn nhất và cao nhất. Tải Input và đáp án tại đây. |
Thời Gian
December 2021
Chủ ĐỀ
All
|