C++에서 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}}}

밖으로 − 3차원 배열의 최소 합 경로:15

설명 - 우리는 길이, 너비, 높이를 가진 정육면체를 받습니다. 이제 3차원 배열에서 최소 합 경로를 계산합니다. 따라서 2 + 4 + 1 + 3 + 5 즉 15에서 시작합니다.

에서 - 정수 입방체[길이][너비][높이] ={ { {1, 2}, {7, 8}}, { {3, 5}, {9, 16}}}

밖으로 − 3차원 배열의 최소 합 경로:24

설명 - 우리는 길이, 너비, 높이를 가진 정육면체를 받습니다. 이제 3차원 배열에서 최소 합 경로를 계산합니다. 따라서 1 + 2 + 5 + 16 즉 24에서 시작합니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

3차원 배열을 입력하여 정수 유형 값으로 큐브를 형성합니다. 데이터를 Minimum_SubPath(cube)로 함수에 전달합니다.
Minimum_SubPath(cube)
함수 내부
- 큐브와 같은 크기의 배열을 만들고 arr[0][0][0]을 큐브[0][0][0]으로 초기화합니다.
- i에서 1까지 FOR 루프를 시작하여 큐브 길이까지 설정하고 arr[i][0][0]을 arr[i-1][0][0] + cube[i][0][0]으로 설정합니다.
- j에서 1까지 FOR 루프를 시작하여 큐브 너비까지 설정하고 arr[0][j][0]을 arr[0][j-1][0] + cube[0][j][0]
- k에서 1까지 FOR 루프를 시작하고 큐브 높이까지 arr[0][0][k]를 arr[0][0][k-1] + cube[0][0][k]
- 큐브의 길이까지 루프 FOR를 i에서 1까지 시작하고 j에서 1까지 배열의 너비까지 다른 루프 FOR를 시작하고 min_val을 Minimum(arr[i-1][j][0], arr[i][ j-1][0], INT_MAX) 및 arr[i][j][0] to min_val + cube[i][j][0]
- 큐브의 길이까지 i에서 1까지 FOR 루프를 시작하고 배열의 높이까지 k에서 1까지 다른 루프 FOR를 시작하고 min_val을 Minimum(arr[i-1][0][k], arr[i][ 0][k-1], INT_MAX) 및 arr[i][0][k] =min_val + 큐브[i][0][k]
- 큐브의 높이까지 k에서 1까지 루프 FOR를 시작하고 배열의 너비까지 j에서 1까지 다른 루프 FOR를 시작하고 min_val을 Minimum(arr[0][j][k-1], arr[0][ j-1][k], INT_MAX) 및 arr[0][j][k] =min_val + 큐브[0][j][k]
- 큐브의 길이까지 루프 FOR를 i에서 1까지 시작하고 j에서 1까지의 또 다른 루프 FOR를 어레이의 너비까지 시작하고 k에서 큐브 높이까지 또 다른 루프를 시작하고 min_val을 Minimum(arr[i-1]로 설정합니다. ][j][k], arr[i][j-1][k], arr[i][j][k-1]) 및 arr[i][j][k] =min_val + 큐브[ i][j][k]
- 반환 arr[길이-1][너비-1][높이-1]
함수 내부 최소(int a, int b, int c)
- b보다 작거나 c보다 작은 경우 IF를 확인한 다음 a를 반환합니다.
- 그렇지 않으면 c를 반환합니다.
- 그렇지 않으면 b가 c보다 작으면 b를 반환
- 그렇지 않으면 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 i, j, k;
   int arr[length][breadth][height];
   arr[0][0][0] = cube[0][0][0];

   for(i = 1; i < length; i++){
      arr[i][0][0] = arr[i-1][0][0] + cube[i][0][0];
   }
   for(j = 1; j < breadth; j++){
      arr[0][j][0] = arr[0][j-1][0] + cube[0][j][0];
   }
   for(k = 1; k < height; k++){
      arr[0][0][k] = arr[0][0][k-1] + cube[0][0][k];
   }
   for(i = 1; i < length; i++){
      for(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(i = 1; i < length; i++){
      for(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(k = 1; k < height; k++){
      for(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(i = 1; i < length; i++){
      for(j = 1; j < breadth; j++){
         for(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