Người Gửi: Dương Lee
- Problem:
Nền phẳng của một công trường 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 một cột bê tông hình hộp có đáy là ô (i, j) và chiều cao là Hij đơn vị. Sau khi dựng xong, thì trời đổ mưa to và đủ lâu. Giả thiết rằng nước không thẩm thấu qua các cột bê tông cũng như không rò rỉ qua các đường ghép giữa chúng.
Yêu cầu: Xác định lượng nước đọng giữa các cột
Chú ý: m, n, Hij là các số nguyên dương. 1 <= m, n <= 100. 1 <= Hij <= 1000
Input
Dòng 1:
|
m n
|
Dòng 2:
|
H11 H12 ... H1n
|
Dòng 3:
|
H21 H22 ... H2n
|
...
|
...
|
Dòng m + 1:
|
Hm1 Hm2 ... Hmn
|
Các số trên 1 dòng các nhau ít nhất 1 dấu cách
Output
Số đơn vị khối nước đọng
Example:
Input
5 5
9 9 9 9 9
9 2 2 2 9
9 2 1 2 9
9 2 2 2 9
9 9 9 9 9
Output:
64
- 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;