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. 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

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++

#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;

}