C++の迷路で目的地に到達する方法の数を数える

行X列行列として表される迷路があり、障害物は-1として表され、クリアセルの値は-1以外です。目標は、最初のセルarr [0] [0]から開始し、最後のセルarr [row] [col]に到達して、2回の移動のみが許可されるようにすることです。

• arr[i][j]を右に移動してarr[i][j+1]に移動します
• arr[i][j]をarr[i+1][j]に下に移動します。

例を挙げて理解しましょう。

入力- arr [row] [col] ={{0、0、0}、{-1、-1、0}、{0、0、0}}

出力- 迷路で目的地に到達する方法の数は次のとおりです：1

説明

0 1 2

0 0 0 0

1 -1 -1 0

2 0 0 0

方法は次のようになります：

• セル（0,0）→セル（0,1）→セル（0,2）→セル（1,2）→セル（2,0）

入力- arr [row] [col] ={{0、0、0、0}、{-1、0、-1、0}、{-1、0、-1、0}、{0、0、0、 0}}

出力- 迷路で目的地に到達する方法の数は次のとおりです：2

説明

0 1 2 3

0 0 0 0 0

1 -1 0 -1 0

2 -1 0 -1 0

3 0 0 0 0

方法は次のようになります：

• セル（0,0）→セル（0,1）→セル（1,1）→セル（2,1）→セル（3,1）→セル（3,2）→セル（3,3 ）
• セル（0,0）→セル（0,1）→セル（0,2）→セル（0,3）→セル（1,3）→セル（2,3）→セル（3,3 ）

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

このアプローチでは、最初にすべてのゼロを1に設定します。迷路マトリックスをもう一度トラバースし、セルごとに、閉塞（-1）の場合は無視します。そうでない場合は、上のセル（i-1、j）と左のセル（i、j-1）を確認します。ゼロより大きい場合は、その値を現在のセル（i、j）に追加します。このようにして、セル（row-1、col-1）に到達するための合計方法として合計を取得します。

• 入力配列arr[row][col]をMazeとして取得します。
• 関数destination_maze（int arr [row] [col]）は、arrを受け取り、迷路で目的地に到達するまでの方法の数を返します。
• 最初のセルがブロックされている場合は、最後に到達する方法として0を返します。
• 次に、左端の列をトラバースし、すべての0を1に設定します。最初は、その下のセルに到達できないため、ブロックによってループが中断されます。インデックスi=0からi
• 同様に、j =0からj
• セル（1,1）からarrを再度トラバースし、arr [i] [j]が-1の場合は、何もしません。
• arr[i-1][j]またはarr[i][j-1]が0より大きい場合、それらからarr[i][j]に到達できます。だから彼らの価値をそれに加えなさい。
• 最後に、それに到達するための完全な方法としてarr[row-1][col-1]があります。
• 0より大きい場合はそれを返し、そうでない場合は0を返します。

例

#include<bits/stdc++.h>

using namespace std;
#define row 3
#define col 3

int destination_maze(int arr[row][col]) {
   if (arr[0][0] == -1) {
      return 0;
   }
   for (int i = 0; i < row; i++) {
      if (arr[i][0] == 0) {
         arr[i][0] = 1;
      } else {
         break;
      }
   }
   for (int i = 1; i < col; i++) {
      if (arr[0][i] == 0) {
         arr[0][i] = 1;
      } else {
         break;
      }
   }
   for (int i = 1; i < row; i++) {
      for (int j = 1; j < col; j++) {
         if (arr[i][j] == -1) {
            continue;
         }
         if (arr[i - 1][j] > 0) {
            arr[i][j] = (arr[i][j] + arr[i - 1][j]);
         }
         if (arr[i][j - 1] > 0) {
            arr[i][j] = (arr[i][j] + arr[i][j - 1]);
         }
      }
   }
   if (arr[row - 1][col - 1] > 0) {
      return arr[row - 1][col - 1];
   } else {
      return 0;
   }
}
int main() {
   int arr[row][col] = {
      {
         0,
         0,
         0
      },
      {
         -1,
         -1,
         0
      },
      {
         0,
         0,
         0
      }
   };
   cout << "Count of number of ways to reach destination in a Maze are: " << destination_maze(arr);
   return 0;
}

上記のコードを実行すると、次の出力が生成されます-

出力

Count of number of ways to reach destination in a Maze are: 1