Tin học Việt

A place for learning and sharing knowledge


    [Bài tập] Các bài tập Pascal về DFS - BFS

    Share

    Admin
    Admin
    Admin

    Posts : 48
    Golds : 2147483647
    Liked : 16
    Ngày tham gia : 2011-08-25
    Tuổi : 20
    Đến từ : Ho Chi Minh City

    [Bài tập] Các bài tập Pascal về DFS - BFS

    Post by Admin on Sun Nov 13, 2011 4:13 pm

    001.SARS
    Spoiler:

    Một cơ quan có N nhân viên được đánh số
    thứ tự từ 1 đến N. Mỗi người có một phòng làm
    việc riêng của mình. Do nhu cầu công việc, hàng ngày mỗi nhân viên có thể phải
    tiếp xúc với một số nhân viên khác. Vào một ngày làm việc bình thường, có một
    nhân viên bị nhiễm bệnh SARS, nhưng do không biết nên người này vẫn đi làm. Đến
    cuối ngày làm việc người ta mới phát hiện ra người nhiễm bệnh SARS đầu tiên.
    Khả năng lây lan của SARS rất nhanh chóng: một người nhiễm bệnh SARS nếu tiếp
    xúc với một người khác có thể sẽ truyền bệnh cho người này.


    Yêu cầu


    Hãy giúp các bác sĩ kiểm tra xem cuối
    ngày hôm đó, có tối đa bao nhiêu người có thể nhiễm bệnh và đó là những người
    nào để còn cách ly. Người có tiếp xúc với người nhiễm bệnh được coi là người
    nhiễm bệnh.


    Dữ liệu


    Dữ liệu vào từ file văn bản SARS.INP.


    Dòng đầu tiên ghi 2 số tự nhiên N và K
    (1<250 1≤K≤N) tương ứng là số lượng người làm việc trong tòa nhà và số
    hiệu của nhân viên đã nhiễm SARS đầu tiên. Dòng thứ I trong N dòng tiếp theo
    ghi danh sách những người có tiếp xúc với người thứ I theo cách sau: số đầu
    tiên J của dòng là tổng số nhân viên đã gặp người thứ I, tiếp theo là J số tự
    nhiên lần lượt là số hiệu của các nhân viên đó. Nếu J=0 có nghĩa rằng không ai
    đã tiếp xúc với người thứ I.


    Kết quả


    Kết quả ghi ra file văn bản SARS.OUT như
    sau:


    Dòng đầu tiên ghi số S là tổng số người
    có thể bị lây nhiễm SARS. Dòng thứ 2 liệt kê tất cả các người có thể bị lây
    nhiễm SARS cần cách ly, danh sách cần được sắp theo thứ tự tăng dần của số hiệu
    nhân viên. Trong file dữ liệu vào và file kết quả, các số trên một dòng cách
    nhau ít nhất một dấu cách.



    Ví dụ:
    SARS.INP
    SARS.OUT
    5 1
    2 2 3
    2 1 3
    1 2
    1 5
    14
    3
    1 2 3







    002.RADAR
    Spoiler:

    Một vùng biển hình chữ nhật được chia lô thành m hàng
    được đánh số từ 1 đến m từ trên xuống dưới và n cột được đánh số từ 1 đến n từ
    trái sang phải. Lô nằm ở vị trí giao của hàng p (1≤ p ≤m) và cột q (1≤ q ≤n)
    được gọi là lô có tọa độ (p, q). Để bảo vệ các giàn khoan dầu trên vùng biển
    này người ta bố trí một số radar tại một số lô. Mỗi radar có khả năng phát hiện
    tầu thuyền tại chính lô đó và 8 lô lân cận (4 lô chung cạnh và 4 lô chung đỉnh)
    kể cả trên biên của các lô này. Một lô trên vùng biển được coi là an toàn nếu
    tàu từ ngoài vùng biển trên muốn vào trong lô đó thì dù đi theo đường đi như
    thế nào cũng đều bị ít nhất một radar phát hiện.


    Yêu cầu: Cho kích thước của vùng biển và vị trí của các lô được bố trí radar.
    Hãy xác định tổng số lô an toàn nằm trong vùng biển này.


    Dữ liệu: Vào từ tệp văn bản RADAR.INP có định dạng như sau:


    • Dòng đầu ghi hai số nguyên dương m và n (1≤
    m, n ≤300) là kích thước (hàng và cột) của vùng biển. Hai số được ghi cách nhau
    một dấu cách.


    • Dòng thứ hai ghi số nguyên k (1 ≤ k ≤ m x
    n) là số các radar được bố trí.


    • Trên dòng thứ i trong k dòng tiếp theo ghi
    hai số nguyên dương p, q (1 ≤ p ≤ m, 1≤ q ≤ n) là tọa độ lô bố trí radar thứ i.
    Hai số được ghi cách nhau một dấu cách.


    Kết quả: Ghi ra tệp văn bản RADAR.OUT một số nguyên dương là tổng số các lô an
    toàn trong vùng biển.


    Ví dụ:

    RADAR.INP
    RADAR.OUT
    8 8
    4
    1 1
    2 4
    4 1
    4 3
    23






    003.NHÀ GƯƠNG CƯỜI

    Spoiler:
    Ban quản lý nhà gương cười muốn thay
    đổi lại toàn bộ các tấm gương phủ tường của nhà gương để phục vụ tốt hơn khách
    tham quan. Nhà gương hiện tại được mô tả bởi bảng ký tự kích
    thước N*N (3≤N≤33). Một số ô của bảng chứa dấu chấm ’.’ để ký hiệu ô trống, một
    số ô khác chứa dấu thăng ’#’ để ký hiệu ô vuông được bao bọc bởi các bức
    tường
    . Tất cả các ô vuông đều có kích thước 3*3 mét.



    Người ta đặt gương xung quanh nhà
    gương, ngoại trừ ô ở góc trên trái và ô ở góc dưới phải tương ứng với lối vào
    và ra của nhà gương. Giả thiết rằng ô ở góc trên trái và dưới phải của bảng
    luôn chứa dấu chấm. Hệ thống gương cũng được đặt bao quanh các ô có tường, tức
    là các ô có dấu thăng.



    Bạn cần giúp ban quản lý tính diện
    tích gương cần mua hay diện tích của các bức tường ở phía trong của nhà gương
    là phần nhìn thấy được bởi du khách vào chơi. Biết rằng chiều cao mỗi bức tường
    đều là 3 mét.



    Dữ liệu: từ tệp MIRROR.INP


    - Dòng đầu tiên chứa số N.


    - N dòng tiếp là các dấu chấm hay
    dấu thăng mô tả nhà gương.



    Kết quả: ghi ra tệp MIRROR.OUT diện tích
    gương cần mua.



    Ví dụ và hình vẽ minh hoạ: Với ví dụ này thì đường nét đậm
    trong hình minh hoạ chính là các vị trí cần đặt gương. Các ô được bôi đen biểu
    thị các ô chứa dấu thăng.



    [You must be registered and logged in to see this image.]



    004.MẠNG GIAO THÔNG


    Spoiler:

    Xét một mạng lưới giao thông bao gồm một tập hợp các nút và các đường dây liên lạc trực tiếp hai chiều giữa các nút. Mạng được xem là liên thông nếu có đường đi giữa mọi cặp nút bất kì.
    Một số nút cung cấp loại dịch vụ A đến tất cả các nút
    liên thông với nó (bao gồm cả chính nó), trong khi một số nút cung cấp loại dịch vụ B cho tất cả các nút liên thông với nó (bao gồm cả chính nó). Cùng một nút có thể cung cấp cả hai loại dịch vụ.

    Đường dây mạng quan trọng là đường dây khi bị ngắt, sẽ dẫn đến gián đoạn việc cung cấp một trong hai loại hình dịch vụ A hoặc B cho một số nút.


    Yêu cầu:
    V
    iết một chương trình để xác định số lượng đường dây mạng quan trọng (Câu A) và cặp nút của mỗi đường dây mạng quan trọng (Câu B).


    Dữ liệu: Cho trong file văn bản MGT.INP:



    • Dòng đầu tiên của file văn bản có chứa bốn số nguyên, N, M, K, và L. N (1 ≤ N ≤ 100 000) là số của các nút mạng. M (1 ≤ M ≤ 1 000 000 ) là số đường dây liên lạc trực tiếp, K (1≤ K ≤ N) là số của các nút cung cấp dịch vụ A, và L (1 ≤ L ≤ N) là số của các nút cung cấp dịch vụ B.
    • Dòng thứ hai chứa các số nguyên K, biểu diễn các nút cung cấp dịch vụ A.
    • Dòng thứ ba chứa số nguyên L, biểu diễn các nút cung cấp dịch vụ B.
    • M dòng tiếp theo có chứa một cặp số nguyên, pq (1 ≤ p, q ≤ N, p ≠ q) cho biết có đường dây nối trực tiếp nút p và nút q. Có nhiều nhất một đường dây liên lạc trực tiếp giữa hai nút bất kỳ.


    Kết quả: Cho trong file văn bản MGT.OUT:


    a)
    Dòng đầu tiên của file văn bản có chứa một số nguyên duy nhất, S, số lượng các đường dây mạng quan trọng .

    b)
    S dòng tiếp theo sau, mỗi dòng có chứa một cặp số nguyên, PQ (1 ≤ p, q ≤ N), xác định một đường dây mạng quan trọng . Thứ tự xuất các đường dây mạng quan trọng là tùy ý.


    Ví dụ:
    MGT.INP
    MGT.OUT
    9
    10 3 4
    2 4 5
    4 9 8 3
    1 2
    4 1
    2 3
    4 2
    1 5
    5 6
    6 7
    6 8
    7 9
    8 7
    3
    3 2
    5 6
    7 9









    Trong ví dụ trên, có nút 4 cung cấp cả 2 loại hình dịch vụ.



    Các đường dây (1,5), (1,2), (1,4) không phải là đường
    dây mạng quan trọng vì khi một trong các đường dây này bị ngắt đi, vẫn đảm bảo
    việc cung cấp cả 2 loại hình dịch vụ A và B cho tất cả các nút.


    [You must be registered and logged in to see this image.]

    GINNY WEASLEY

    Posts : 1
    Golds : 1
    Liked : 0
    Ngày tham gia : 2013-02-13

    Re: [Bài tập] Các bài tập Pascal về DFS - BFS

    Post by GINNY WEASLEY on Thu Feb 14, 2013 2:41 pm

    Có vẻ lâu lắm rồi không ai vào Forum này nhỉ ?
    Bạn Admin có thể cho mình xinh Code đáp án của những bài trên không
    Thanks bạn

      Current date/time is Tue Dec 06, 2016 3:39 am