QN4 - Tránh lụt ^^
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 20.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: duytoannguyenledh

Tránh lụt 

Bản đồ của một thành phố được vẽ thành một bảng gồm NxM ô, tượng trưng cho NxM khu vực. Hai khu vực có thể đi qua lại được nếu có chung một cạnh. Ở mỗi khu vực có một số nguyên cho biết độ cao của khu vực đó.

Vào mùa lũ những năm qua, có một số khu vực của thành phố bị ngập và một số khu vực chưa bị ngập. Các khu vực chưa bị ngập liên kết với nhau tạo thành các “đảo”. Hai khu vực X, Y gọi là nằm trên cùng một “đảo” nếu có đường đi giữa X và Y thông qua các khu vực chưa bị ngập.

Yêu cầu: Bạn hãy lập trình giúp người dự báo tránh lụt cho nhân dân trong thành phố, bằng cách cho họ biết số “đảo” mỗi năm khi mùa lụt đến.

Dữ liệu vào: Gồm các dòng:

- Dòng 1 ghi 2 số nguyên dương N, M ( 1 ≤ N, M ≤ 1000 ).

- N dòng tiếp theo, mỗi dòng ghi M số nguyên dương cho biết độ cao của các khu vực.

- Dòng thứ N+2 ghi 1 số nguyên T cho biết số lượng năm ( 1 ≤ T ≤ 105).

- Dòng thứ N+3 ghi T số nguyên Hi cho biết mực nước lũ về các năm (0 ≤ H1 ≤ H2 ≤ H3 ... ≤ HT).

Dữ liệu ra: Gồm 01 dòng ghi T số nguyên tương ứng với số lượng “đảo” các năm và đặt cách nhau bởi dấu cách.

Ví dụ:

BL4.INP

BL4.OUT

4 5

1 2 3 3 1

1 3 2 2 1

2 1 3 4 3

1 2 2 2 2

5

1 2 3 4 5

2 3 1 0 0

Ví dụ

Back to Top