150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 6

081. MÊ CUNGBản đồ mê cung có dạng hình chữ nhật kích thước mxn được chia thành lưới ô vuông đơn vị bằng các đường song song với các cạnh (m hàng, n cột). Mỗi ô vuông của bản đồ được đánh dấu hoặc là ô cấm, hoặc là ô tự do. Từ một ô tự do có thể di chuyển sang các ô tự do có chung cạnh với nó. Không được phép di chuyển vượt khỏi biên của mê cung.
Nội dung trích xuất từ tài liệu:
150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 6 081. MÊ CUNGBản đồ mê cung có dạng hình chữ nhật kích thước mxn được chia thành lưới ô vuông đơn vị bằngcác đường song song với các cạnh (m hàng, n cột). Mỗi ô vuông của bản đồ được đánh dấu hoặc làô cấm, hoặc là ô tự do. Từ một ô tự do có thể di chuyển sang các ô tự do có chung cạnh với nó.Không được phép di chuyển vượt khỏi biên của mê cung.Mê cung được thiết kế khá đặc biệt, giữa hai ô tự do bất kỳ chỉ có duy nhất một cách di chuyển từô này đến ô kia mà trong quá trình di chuyển không đi tới bất kỳ ô nào quá một lần. Tại tâm củamỗi ô tự do đều có một cái móc. Trong mê cung có hai ô tự do đặc biệt, mà nếu bạn nối được haicái móc ở hai ô đó bằng một sợi dây thừng (tất nhiên phải nối qua các móc của các ô trung gian) thìcánh cửa bí mật của mê cung sẽ tự mở ra.Vấn đề đặt ra là phải chu n bị một sợi dây thừng với độ dài ngắn nhất đảm bảo cho dù hai ô đặcbiệt có nằm ở vị trí nào trong mê cung, bạn vẫn có thể nối được hai cái móc ở hai ô đó bằng sợidây đã chu n bị.Dữ liệu: Vào từ file văn bản LABYR.INPDòng đầu tiên chứa hai số n, m (3 ≤ m, n ≤ 1000)Các dòng tiếp theo mô tả mê cung, dòng thứ i trong số m dòng tiếp theo chứa n ký tự, mỗi ký tự chỉlà # hoặc .. Trong đó ký tự # cho biết ô ở vị trí tương ứng là bị cấm, còn ký tự . cho biết ô ởvị trí tương ứng là tự do (1 ≤ i ≤ m).Kết quả: Ghi ra trên một dòng của file văn bản LABYR.OUT độ dài của sợi dây thừng cần chuNnbị .Ví dụ: LABYR.INP LABYR.OUT LABYR.INP LABYR.OUT ### 0 8 10 29 #.# ######## ### .......# .#.#.#.# .#####.# #....#.# #.##.#.# #.##...# #.#.##.# #.#.##.# #.....## 91 082. DU L CH KI U ÚCMột khu thắng cảnh gồm n điểm đánh số từ 1 tới n (n ≤ 200) và m đường đi hai chiều nối giữa cáccặp địa điểm đó. Giữa hai cặp địa điểm có nhiều nhất là một đường đi trực tiếp. Có hai địa điểm đặcbiệt: A và B.Một Tour du lịch là một hành trình của du khách: Trước hết là đáp máy bay xuống địa điểm A, sauđó đi bộ theo các đường hai chiều đã cho để tới địa điểm B, và lại đi bộ quay trở về địa điểm xuấtphát A để rồi quay về bằng máy bay. Để tránh sự nhàm chán cho du khách, hành trình không đượcđi qua đoạn đường nào nhiều hơn một lần.Vấn đề đặt ra là một du khách có thể đến thăm khu thắng cảnh nhiều lần. Để phục vụ khách tham quan tốt hơn. Hãy tìm một số tour du lịch nhiều nhất sao cho hai tour du lịch bất kỳ tìm được đều không tồn tại một đoạn đường nào chung.Dữ liệu: Vào từ file văn bản TOURS.INP• Dòng 1: Ghi bốn số n, m, A, B• m dòng tiếp theo mỗi dòng có dạng x y cho biết giữa hai địa điểm x và y có đường đi trực tiếp.Kết quả: Ghi ra file văn bản TOURS.OUT• Dòng 1: Ghi số k là số tour du lịch tìm được• k dòng tiếp theo, dòng thứ i mô tả tour du lịch thứ i: bắt đầu từ địa điểm A tiếp theo là danh sách các địa điểm theo thứ tự trong hành trình tới địa điểm B và tiếp theo là danh sách các địa điểm theo thứ tự trong hành trình quay trở lại địa điểm A. (Như vậy địa điểm A là địa điểm chắc chắn phải được liệt kê hai lần).Các số trên một dòng của Input/Output file được ghi cách nhau ít nhất một dấu cáchVí dụ:TOURS.INP TOURS.OUT5 10 1 2 2 113 123124 1425135 5 24152122334 4 34551 92 083. S A ĐƯ NGTrong một thành phố có n nút giao thông và m đường phố hai chiều. Giữa hai nút giao thông cónhiều nhất là một đường phố nối chúng. Hệ thống giao thông đảm bảo sự đi lại giữa hai nút bất kỳ.Sau một thời gian dài, các đường phố xuống cấp nghiêm trọng đòi hỏi ban quản lý giao thông vàcông trình đô thị phải lên kế hoạch nâng cấp tất cả các đường phố. Khi một đường phố đang trongthời gian nâng cấp thì sự đi lại trên tuyến đường đó bị cấm. Xét về khả năng, với phương tiện kỹthuật hiện đại và lực lượng nhân công dồi dào, người ta có thể tiến hành nâng cấ ...