Đề th PASCAL ứng dụng đồ thị

Hệ thống đảo cung cấp xăng
Có N hòn đảo đánh số từ 1 đến N. xi, yi là tọa độ hòn đảo thứ i. Trên mỗi đảo có bể chứa xăng có khả năng cung cấp đầy các thiết bị chứa xăng của ca nô. Biết rằng các thiết bị chứa xăng của ca nô không thể chứa đủ số xăng đi hết M Km.
Hãy tìm hành trình cho ca nô đi từ một đảo U đến đảo V (0Dữ liệu vào từ file Dao.inp: Dòng đầu ghi 4 số nguyên dương N, M, U, V. Các dòng tiếp theo, dòng thứ i trong các dòng này ghi 2 số nguyên dương xi, yi.
Kết quả ghi ra file Dao.out: Nếu có đường đi thì dòng đầu tiên ghi số đảo ghé vào lấy xăng (trừ U và V). Dòng thứ hai ghi số hiệu các đảo đó theo thứ tự hành trình. Nếu không có đường đi thì ghi “NO SULUTION”

DAO.IN
DAO.OUT

12 10 1 12
0 0
8 0
8 6
0 8
10 4
15 4
20 8
20 0
25 8
25 4
25 0
30 4
4
2 6 7 9


Bài Road
Có N thành phố. Trên một mặt phẳng tọa độ, mỗi thành phố coi là một điểm. Tọa độ của các điểm này có giá trị tuyệt đối nhỏ hơn 30.000. Người ta muốn xây dựng các con đường từ thành phố này tới thành phố khác. Bản thiết kế xây dựng có các tính chất sau: Không có 3 thành phố nào nằm trên một con đường, có không quá N-1 con đường, các con đường có thể giao nhau (do đó bạn có thể chuyển sang con đường khác hoặc đi thẳng nếu gặp điểm giao). Bạn hãy lập trình kiểm tra xem từ thành phố 1 ta có thể đi đến được những thành phố nào.
Dữ liệu vào từ file Road.in:
Dòng thứ nhất chứa 2 số nguyên dương N, M (N<200), M là số con đường.
N dòng tiếp theo mỗi dòng 2 số nguyên mô tả tọađộ của 1 thành phố
M dòng tiếp theo mỗi dòng 2 số i, j mô tả có tuyến đường gữa 2 thành phố i và j
Kêt quả ghi ra file road.out:
Dòng đầu là số K: số thành phố đến được từ thành phố 1
Dòng 2 là K số nguyên là các thành phố đến được (theo thứ tự từ nhỏ đến lớn).
Ví dụ:
ROAD.IN
ROAD.OUT
ROAD.IN
ROAD.OUT

4 2
0 0
1 0
0 1
1 1
1 4
2 3
4
1 2 3 4
4 2
0 0
1 0
0 1
1 1
1 2
3 4
2
1 2






Lâu đài
 



Hình 1.(chuỗi ký tự * là các bức tường)
Hình 1 là bản đồ một lâu đài.
Lâu đài được chia thành lưới ô vuông gồm m hàng và n cột ( m<= 50, n<=50). Mỗi ô vuông có thể có từ 0 đến 4 bức tường bao quanh.
Hãy viết chương trình tính:
1) Số phòng trong lâu đài.
2) Kích thước của căn phòng lớn nhất.
Dữ liệu vào
Bản đồ lâu đài được lưu trong tệp INPUT.TXT dưới dạng các số, mỗi số tương ứng với 1 ô vuông.
 
* Tệp này chứa: đầu tiên là số ô vuông theo hướng bắc-nam và số ô vuông theo hướng đông-tây.
 
* Trên các dòng tiếp theo, mỗi ô vuông được mô tả bằng một số p (0<=p<=15). Số này là tổng của: 1 (= bức tường phía tây), 2 (= bức tường phía bắc), 4(= bức tường phía đông), 8(= bức tường phía nam). Các bức tường bên trong được định nghĩa hai lần: một bức tường phía nam của ô vuông (1,1) cũng chính là bức ở phía bắc của ô vuông (2,1). Ô vuông (1,1) có các bức tường ở phía tây, bắc và nam do đó tổng là 1 + 2 + 8 = 11.
Lâu đài luôn có ít nhất hai phòng.
  
Kết quả:
Output được lưu trong tệp OUTPUT.TXT với hai dòng:
1) Số phòng.
2) Diện tích căn phòng lớn nhất tính theo số ô vuông.
INPUT.TXT
OUTPUT.TXT

4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13