home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Minimum Sum Path ในอาร์เรย์ 3 มิติ (3-D Array) ใน C++

ได้รับลูกบาศก์ (cube) ที่สร้างจากอาร์เรย์ 3 มิติ cube[length][breadth][height] หา minimum sum path จากการเดินทางผ่านลูกบาศก์

ตัวอย่าง

Input: cube 3×3×3 = {{{2,4,1},{3,4,5},{9,8,7}}, {{5,3,2},{7,6,5},{8,7,6}}, {{3,2,1},{4,3,2},{5,4,3}}}

Output: Minimum Sum Path In 3-D Array are: 15

คำอธิบาย: เส้นทาง: 2 + 4 + 1 + 3 + 5 = 15

Input: cube 2×2×2 = {{{1,2},{7,8}}, {{3,5},{9,16}}}

Output: Minimum Sum Path In 3-D Array are: 24

คำอธิบาย: เส้นทาง: 1 + 2 + 5 + 16 = 24

อัลกอริทึม: Dynamic Programming 3 มิติ

  • สร้างอาร์เรย์ arr ขนาดเท่า cube, เริ่ม arr[0][0][0] = cube[0][0][0]
  • เติมขอบ (edges) ก่อน:
    • arr[i][0][0] = arr[i-1][0][0] + cube[i][0][0] (แกน length)
    • arr[0][j][0] = arr[0][j-1][0] + cube[0][j][0] (แกน breadth)
    • arr[0][0][k] = arr[0][0][k-1] + cube[0][0][k] (แกน height)
  • เติมหน้า (faces) โดยใช้ Minimum(a,b,INT_MAX):
    • arr[i][j][0] = min(arr[i-1][j][0], arr[i][j-1][0]) + cube[i][j][0]
    • arr[i][0][k] = min(arr[i-1][0][k], arr[i][0][k-1]) + cube[i][0][k]
    • arr[0][j][k] = min(arr[0][j][k-1], arr[0][j-1][k]) + cube[0][j][k]
  • เติมภายใน (interior): arr[i][j][k] = min(arr[i-1][j][k], arr[i][j-1][k], arr[i][j][k-1]) + cube[i][j][k]
  • คืนค่า arr[length-1][breadth-1][height-1]

ฟังก์ชัน Minimum(a,b,c)

คืนค่าต่ำสุดของ 3 ตัว

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

#include <bits/stdc++.h>
using namespace std;
#define length 3
#define breadth 3
#define height 3

int Minimum(int a, int b, int c) {
    if (a < b) {
        if (a < c) return a;
        else return c;
    } else if (b < c) return b;
    else return c;
}

int Minimum_SubPath(int cube[][breadth][height]) {
    int arr[length][breadth][height];
    arr[0][0][0] = cube[0][0][0];
    for (int i = 1; i < length; i++)
        arr[i][0][0] = arr[i-1][0][0] + cube[i][0][0];
    for (int j = 1; j < breadth; j++)
        arr[0][j][0] = arr[0][j-1][0] + cube[0][j][0];
    for (int k = 1; k < height; k++)
        arr[0][0][k] = arr[0][0][k-1] + cube[0][0][k];
    for (int i = 1; i < length; i++)
        for (int j = 1; j < breadth; j++) {
            int min_val = Minimum(arr[i-1][j][0], arr[i][j-1][0], INT_MAX);
            arr[i][j][0] = min_val + cube[i][j][0];
        }
    for (int i = 1; i < length; i++)
        for (int k = 1; k < height; k++) {
            int min_val = Minimum(arr[i-1][0][k], arr[i][0][k-1], INT_MAX);
            arr[i][0][k] = min_val + cube[i][0][k];
        }
    for (int k = 1; k < height; k++)
        for (int j = 1; j < breadth; j++) {
            int min_val = Minimum(arr[0][j][k-1], arr[0][j-1][k], INT_MAX);
            arr[0][j][k] = min_val + cube[0][j][k];
        }
    for (int i = 1; i < length; i++)
        for (int j = 1; j < breadth; j++)
            for (int k = 1; k < height; k++) {
                int min_val = Minimum(arr[i-1][j][k], arr[i][j-1][k], arr[i][j][k-1]);
                arr[i][j][k] = min_val + cube[i][j][k];
            }
    return arr[length-1][breadth-1][height-1];
}

int main() {
    int cube[length][breadth][height] = {
        {{2,4,1},{3,4,5},{9,8,7}},
        {{5,3,2},{7,6,5},{8,7,6}},
        {{3,2,1},{4,3,2},{5,4,3}}
    };
    cout << "Minimum Sum Path In 3-D Array are: " << Minimum_SubPath(cube);
    return 0;
}

ผลลัพธ์

Minimum Sum Path In 3-D Array are: 15