Link Sub: http://vn.spoj.com/problems/PBCWATER/Người Gửi: Dương Lee
- Problem:
Nền phẳng của 1 công trình xây dựng được chia thành lưới ô vuông đơn vị kích thước MxN ô. Trên mỗi ô (i,j) của lưới, người ta dựng 1 cột bê tông hình hộp có đáy là ô (i,j) và chiều cao là h[i,j] đơn vị. Sau khi dựng xong thì trời đổ mưa to và đủ lâu. Nhà thầu xây dựng muốn tính lượng nước đọng lại giữa các cột để có kế hoạch thi công tiếp theo. Giả thiết, nước ko thẩm thấu qua các cột bê tông cũng như ko rò rỉ qua các đường ghép giữa chúng.
Nhiệm vụ của bạn là giúp nhà thầu tính toán lượng nước đọng lại giữa các cột.
Input
Dòng đầu tiên ghi 2 số nguyên dương M và N
Dòng thứ i trong M dòng tiếp theo, ghi N số nguyên dương h[i,1],h[i,2]...h[i,N].
Giới hạn: 1<=M,N<=100,1<=H[i,j]<=1000
Output
1 dòng duy nhất chứa số đơn vị khối nước đọng lại.
Example:
Input
5 5
9 9 9 9 9
9 2 2 2 9
9 2 5 2 9
9 2 2 2 9
9 9 9 9 9
Output:
60
- Solution:
*Ý tưởng:
- Ta xét từng phân khúc từ dưới lên (giống chặt cây thành từng đoạn có độ cao là 1);
- Xét đường biên nếu biên thấp hơn bên trong thì đánh dấu bên trong không có nước đọng.
- Duyệt lại và đếm xem có bao nhiêu ô có nước đọng.
*Thực hiện:
- Tạo mảng riêng H_Sp với các chỉ số 0 và 1;
- Mảng riêng có đặc điểm:
+ Tại hàng i, cột j: H[i][j]<1?H_Sp[i][j]=0:H_Sp[i][j]=1; và H[i][j]--;
VD:
1 1 0
3 0 2
1 1 1
-> Chặt lần 1 sẽ thu được:
H_Sp:
1 1 0
1 0 1
1 1 1
H:
0 0 0
2 0 1
0 0 0
+ Sẽ chặt cho đến khi Hmax =0;
+ Với mỗi H_Sp thu được sẽ duyệt đường biên nếu biên H_Sp[i][j]==0? thì có nghĩa là đường biên này đang thấp hơn các cột khác. -> Ta sẽ loang từ biên loang vào 4 phía, đánh dấu các ô ==0 -> 1 (Bước này dùng để xác định tại các ô đó sẽ không có nước đọng)
VD: với H_Sp trên khi loang vào sẽ được:
1 1 1
1 0 1
1 1 1
+ Cuối cùng thì chỉ cần duyệt lại mảng H_Sp để đếm các ô ==0 (nước đọng) và lặp lại quá trình cho đến Hmax=0;