BCSON spoj PTIT – Sơn cột
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCSON/ 1. Đề bài BCSON spoj PTIT Trên một nền phẳng đã được chia thành các lưới ô vuông đơn vị gồm mxn ô, người ta đặt chồng khít lên nhau các khối lập phương đơn vị thành những cột. Khối dưới cùng của cột chiếm trọn một ô của lưới. ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCSON/
1. Đề bài BCSON spoj PTIT
Trên một nền phẳng đã được chia thành các lưới ô vuông đơn vị gồm mxn ô, người ta đặt chồng khít lên nhau các khối lập phương đơn vị thành những cột. Khối dưới cùng của cột chiếm trọn một ô của lưới. Chiều cao của mỗi cột được tính bằng số khối lập phương đơn vị tạo thành cột đó. Sau khi xếp xong toàn bộ các cột, người ta tiến hành sơn các mặt nhìn thấy được của các cột.
Yêu cầu: Biết chiều cao của mỗi cột, hãy tính số đơn vị diện tích cần sơn.
Dữ liệu:
l Dòng đầu tiên chứa hai số nguyên dương m, n ≤ 1000 là kích thước của lưới nền (m hàng, n cột)
l m dòng tiếp theo, dòng thứ i chứa n số nguyên dương có giá trị không quá 109, số thứ j biểu thị chiều cao của cột dựng tại ô ở hàng i, cột j của lưới.
Các số trên một dòng của Input file cách nhau ít nhất một dấu cách
Kết quả: Ghi ra một số nguyên duy nhất là diện tích cần sơn.
Example
Input:
2 3
4 3 4
1 2 1
Output:
42
2. Giải thuật sơn cột BCSON spoj PTIT
Với bài này thì bạn cần xét các vị trí trên, dưới, trái phải, của mỗi mỗi cột, nếu nó cao hơn các vị trí xung quanh bao nhiêu thì cần sơn bấy nhiêu.
Và tính cả mặt trên của cột thì giá trị cần sơn phải cộng thêm số cột.
Ở đây mình sẽ tạo ra 1 đường viền xung quanh các cột, giá trị của nó sẽ là 0 hết, để tính các trường hợp các cột ở biên.
3. Code tham khảo BCSON spoj PTIT
a. Code pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | const fi='; nmax=1000; type data=longint; var f:text; A:array[0..nmax+1,0..nmax+1] of data; n,m:data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,m,n); for i:=1 to m do for j:=1 to n do read(f,a[i,j]); for i:=0 to m+1 do begin A[i,0]:=0; A[i,n+1]:=0; end; for i:=0 to n do begin A[0,i]:=0; A[m+1,i]:=0; end; close(f); end; procedure xuli; var i,j:data; s:int64; begin s:=M*N; for i:=1 to m do for j:=1 to n do begin if a[i,j]>a[i-1,j] then inc(s,a[i,j]-a[i-1,j]); if a[i,j]>a[i+1,j] then inc(s,a[i,j]-a[i+1,j]); if a[i,j]>a[i,j-1] then inc(s,a[i,j]-a[i,j-1]); if a[i,j]>a[i,j+1] then inc(s,a[i,j]-a[i,j+1]); end; writeln(s); end; begin docfile; xuli; end. |
b. Code c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <iostream> using namespace std; int main() { int n,m; long long s=0; cin >> m >> n; s=m*n; long a[m+2][n+2]; for(int i=0;i<m+2;i++) for(int j=0;j<n+2;j++) { if(i==0||i==m+1||j==0||j==n+1) a[i][j]=0; else cin >> a[i][j]; } for(int i=1;i<m+1;i++) for(int j=1;j<n+1;j++) { if(a[i][j]>a[i-1][j]) s+=(a[i][j]-a[i-1][j]); //vi tri tren if(a[i][j]>a[i+1][j]) s+=(a[i][j]-a[i+1][j]); //vi tri duoi if(a[i][j]>a[i][j-1]) s+=(a[i][j]-a[i][j-1]); //vi tri trai if(a[i][j]>a[i][j+1]) s+=(a[i][j]-a[i][j+1]); //vi tri phai } cout << s; } |
