C++の3D配列の最小合計パス

3D配列を使用して形成できる立方体がcube[length][breadth][height]として与えられます。タスクは、キューブをトラバースすることによって達成される最小合計パスを計算し、結果を出力することです。

このためのさまざまな入出力シナリオを見てみましょう-

で − 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}}}

アウト −3Dアレイの最小合計パスは次のとおりです。15

説明 −長さ、幅、高さのある立方体が与えられます。次に、3D配列の最小合計パスを計算します。したがって、2 + 4 + 1 + 3 + 5、つまり15から始まります。

で − int cube [length] [breadth] [height] ={{{1、2}、{7、8}}、{{3、5}、{9、16}}}

アウト −3Dアレイの最小合計パスは次のとおりです。24

説明 −長さ、幅、高さのある立方体が与えられます。次に、3D配列の最小合計パスを計算します。したがって、1 + 2 + 5 + 16、つまり24から始まります。

以下のプログラムで使用されているアプローチは次のとおりです

• 3D配列を入力して、整数型の値を持つキューブを形成します。データをMinimum_SubPath（cube）として関数に渡します。

• 関数Minimum_SubPath（cube）

  の内部

  • キューブと同じサイズの配列を作成し、arr [0][0][0]をcube[0][0][0]に初期化します。

  • ループFORをiから1までキューブの長さまで開始し、arr [i][0][0]をarr[i-1][0] [0] + cube [i][0][0]に設定します。

  • ループFORをjから1までキューブの幅まで開始し、arr [0][j][0]をarr[0][j-1] [0] + cube [0] [j][0]

  • ループFORをkから1までキューブの高さまで開始し、arr [0][0][k]をarr[0][0] [k-1] + cube [0] [0][k]

  • 立方体の長さまでiから1までループFORを開始し、配列の幅までjから1まで別のループFORを開始し、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]

  • 立方体の長さまで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 + cube [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 + cube [0] [j] [k]

  • 立方体の長さまでiから1までループFORを開始し、配列の幅までjから1まで別のループFORを開始し、立方体の高さまでkから1まで別のループを開始し、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]

  • arr [length-1] [breadth-1] [height-1]

    を返します

• 関数Minimum（int a、int b、int c）の内部

  • b未満およびc未満の場合はチェックしてから、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