C++でのマトリックスの幅優先探索

特定のマトリックスには、要素の位置を分析するための4つのオブジェクトがあります。左、右、下、上です。

幅優先探索は、特定の2次元行列の2つの要素間の最短距離を見つけることに他なりません。したがって、各セルには、実行できる4つの操作があり、次のように4つの数字で表すことができます。

• 「2」は、マトリックス内のセルがソースであることを示します。
• 「3」は、マトリックス内のセルが宛先であることを示します。
• 「1」は、セルをある方向にさらに移動できることを示します。
• 「0」は、マトリックス内のセルをどの方向にも移動できないことを示します。

アドビの正当化に基づいて、特定のマトリックスに対して幅優先探索操作を実行できます。

この問題を解決するためのアプローチ

マトリックス全体をトラバースし、BFSを使用してセル間の最小距離または最短距離を見つけるアルゴリズムは次のとおりです。

• 最初に入力行と列を取得します。
• 指定された行と列で行列を初期化します。
• 整数関数shortestDist（int row、int col、int mat [] [col]）は、行、列、および行列を入力として受け取り、行列の要素間の最短距離を返します。
• 変数のソースと宛先を初期化して、ソースと宛先要素を見つけます。
• 要素が「3」の場合は宛先としてマークし、要素が「2」の場合はソース要素としてマークします。
• 次に、キューのデータ構造を初期化して、指定されたマトリックスに幅優先探索を実装します。
• キュー内のマトリックスの行と列をペアで挿入します。次に、セル内を移動して、それが宛先セルであるかどうかを確認します。宛先セルの距離が現在のセルよりも小さいか小さい場合は、距離を更新します。
• もう一度別の方向に移動して、現在のセルからのセルの最小距離を確認します。
• 最小距離を出力として返します。

例

#include<bits/stdc++.h>
using namespace std;
int findDistance(int row, int col, int mat[][5]) {
   int source_i, source_j, destination_i, destination_j;
   for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
         if (mat[i][j] == 2) {
            source_i = i;
            source_j = j;
         }
         if (mat[i][j] == 3) {
            destination_i = i;
            destination_j = j;
         }
      }
   }
   int dist[row][col];
   for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++)
         dist[i][j] = INT_MAX;
   }
   // initialise queue to start BFS on matrix
   queue < pair < int, int >> q;
   q.push(make_pair(source_i, source_j));
   dist[source_i][source_j] = 0;

   // modified BFS by add constraint checks
   while (!q.empty()) {
      // storing the x co-ordinate or row information of cell
      int x = q.front().first;
      // storing the y co-ordinate or column information of cell
      int y = q.front().second;
      // Remove the cell from queue
      q.pop();

      // If move towards left is allowed or it is the destnation cell
      if (y - 1 >= 0 && (mat[x][y - 1] == 1 || mat[x][y - 1] == 3)) {
         // if distance to reach the cell to the left is less than the computed previous path distance, update it
         if (dist[x][y] + 1 < dist[x][y - 1]) {
            dist[x][y - 1] = dist[x][y] + 1;
            q.push(mkp(x, y - 1));
         }
      }
      // If move towards right is allowed or it is the destination cell
      if (y + 1 < col && (mat[x][y + 1] == 1 || mat[x][y + 1] == 3)) {
         // if distance to reach the cell to the right is less than the computed previous path distance, update it
         if (dist[x][y] + 1 < dist[x][y + 1]) {
            dist[x][y + 1] = dist[x][y] + 1;
            q.push(mkp(x, y + 1));
         }
      }
      // If upward direction is allowed
      if (x - 1 >= 0 && (mat[x - 1][y] == 1 || mat[x - 1][y] == 3)) {
         if (dist[x][y] + 1 < dist[x - 1][y]) {
            dist[x - 1][y] = dist[x][y] + 1;
            q.push(mkp(x - 1, y));
         }
      }

      // If downward direction allowed
      if (x + 1 < row && (mat[x + 1][y] == 1 || mat[x + 1][y] == 3)) {
         // if distance to reach the cell to the down is less than the computed previous path distance, update it
         if (dist[x][y] + 1 < dist[x + 1][y]) {
            dist[x + 1][y] = dist[x][y] + 1;
            q.push(mkp(x + 1, y));
         }
      }
   }
   return dist[destination_i][destination_j];
}

int main() {
   // initialising number of rows and columns
   int row = 5;
   int col = 5;
   // initialising matrix
   int mat[][5] = {
      {1, 0, 0, 2, 1},
      {1, 0, 1, 1, 1},
      {0, 1, 1, 2, 0},
      {3, 1, 0, 0, 1},
      {1, 1, 0, 0, 1}
   };
   int answer = findDistance(row, col, mat);
   // When source and destination are unreachable
   if (answer == INT_MAX)
      cout << "No Path Found" << endl;
   else {
      cout << "The Shortest Distance between Source and Destination is:" << endl;
      cout << answer << endl;
   }
   return 0;
}

出力

The Shortest Distance between Source and Destination is:4