หาพื้นที่ผิวของรูปทรง 3 มิติจากเมทริกซ์ความสูงใน Python

คำนวณพื้นที่ผิวของรูปทรง 3 มิติจาก Height Map

กำหนดเมทริกซ์ N x M ที่ A[i][j] = ความสูงของอาคารที่ตำแหน่ง (i,j) ต้องการหาพื้นที่ผิวรวมของรูปทรง 3 มิตินี้

สูตร: พื้นที่ผิว = ผลรวมของความต่างความสูงระหว่างเซลล์ติดกัน (แนวตั้งและแนวนอน) + พื้นที่ด้านบนและด้านล่าง (2*N*M)

อัลกอริทึม

1. วนทุกเซลล์ (i, j)
2. หาความสูงของเพื่อนบน (up) และซ้าย (left) ถ้ามี
3. บวก |A[i][j] - up| + |A[i][j] - left|
4. ถ้าอยู่ขอบล่างสุด บวก A[i][j] (ด้านหน้า)
5. ถ้าอยู่ขอบขวาสุด บวก A[i][j] (ด้านขวา)
6. สุดท้ายบวก 2*N*M (ด้านบน + ด้านล่าง)

โค้ดตัวอย่าง Python

def get_surface_area(grid):
    if not grid:
        return 0
    N = len(grid)
    M = len(grid[0])
    res = 0
    for i in range(N):
        for j in range(M):
            up = grid[i-1][j] if i > 0 else 0
            left = grid[i][j-1] if j > 0 else 0
            res += abs(grid[i][j] - up) + abs(grid[i][j] - left)
            if i == N - 1:
                res += grid[i][j]
            if j == M - 1:
                res += grid[i][j]
    res += N * M * 2
    return res

grid = [[1, 4, 5],
        [3, 3, 4],
        [1, 3, 5]]
print(get_surface_area(grid))  # 72