C++の迷路でコーナーセルからミドルセルへのパスを検索する

数字で満たされた正方形の迷路があるとします。コーナーセルから中央セルまでのすべてのパスを見つける必要があります。ここでは、セルから上、下、右、左の4方向に正確にnステップ進みます。ここで、nはセルの値です。したがって、セル[i、j]からセル[i + n、j]から[i-n、j]、[i、j + n]、および[i、j-n]に移動できます。ここで、nはセル[の値です。 i、j]。

したがって、入力が次のような場合

その場合、出力は次のようになります

• （0、0）→（0,3）→（0,7）→（6,7）→（6,3）→（3,3）→（3,4）→（5,4）→（5 、2）→（1,2）→（1,7）→（7,7）→（7,1）→（2,1）→（5,1）→（0,1）→（4,1 ）→（4、4）→中程度

• （0、0）→（0,3）→（0,7）→（6,7）→（6,3）→（3,3）→（3,4）→（5,4）→（5 、2）→（1、2）→（1、7）→（7,7）→（7,1）→（2,1）→（2,4）→（4,4→MIDDLE

• （0、0）→（0,3）→（0,7）→（0,1）→（4,1）→（7,1）→（2,1）→（2,4）→（4 、4）→中程度

• （0、0）→（0,3）→（0,7）→（0,1）→（4,1）→（4,4）→MIDDLE

• （8、8）→（7,8）→（4,8）→（4,4）→MIDDLE

これを解決するには、次の手順に従います-

• N：=9

• 関数is_ok（）を定義します。これには、visited、1ペアpt、

  と呼ばれるペアのセットが1つ必要です。

• ptの1番目と2番目の要素が0からNの範囲にあり、ptが訪問されていない場合にtrueを返します

• 配列を定義しますdir_row：={-1、1、0、0}

• 配列を定義しますdir_col：={0、0、-1、1} ​​

• 配列行を定義します：={0、0、N-1、N-1}

• 配列colを定義します：={0、N-1、0、N-1}

• 関数solve（）を定義します。これにより、迷路、パス、訪問したペアの1セット、ペアのcurrが1つ取得されます。

• currの1番目と2番目がN/2と同じ場合、-

  • パスを表示する

  • 戻る

• 初期化i：=0の場合、i <4の場合、更新（iを1増やします）、実行-

  • n：=迷路[curr.first、curr.second]

  • x：=curr.first + dir_row [i] * n

  • y：=curr.second + dir_col [i] * n

  • n：=x、yを使用したペア

  • is_ok（visited、next）の場合、-

    • 次に訪問先に挿入

    • パスの最後に次を挿入

    • 解決（迷路、パス、訪問、次）

    • パスから最後の要素を削除する

    • 訪問済みから次を削除

• メインの方法から、次のようにします-

• 訪問済みと呼ばれるペアの1つのセットを定義します

• 初期化i：=0の場合、i <4の場合、更新（iを1増やします）、実行-

  • x：=row [i]

  • y：=col [i]

  • pt：=（x、y）を使用してペアを作成する

  • 訪問先にptを挿入

  • パスの最後にptを挿入します

  • 解決（迷路、パス、訪問済み、pt）

  • パスから最後の要素を削除する

  • 訪問先からptを削除

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
#define N 9
bool is_ok(set<pair<int, int> > visited, pair<int, int> pt) {
   return (pt.first >= 0) && (pt.first < N) && (pt.second >= 0) && (pt.second < N) && (visited.find(pt) == visited.end());
}
void display_path(list<pair<int, int> > path) {
   for (auto it = path.begin(); it != path.end(); it++)
   cout << "(" << it->first << ", " << it->second << ")->";
   cout << "MIDDLE" << endl << endl;
}
int dir_row[] = {-1, 1, 0, 0};
int dir_col[] = { 0, 0, -1, 1};
int row[] = { 0, 0, N-1, N-1};
int col[] = { 0, N-1, 0, N-1};
void solve(int maze[N][N], list<pair<int, int> > &path, set<pair<int, int> > &visited, pair<int, int> &curr) {
   if (curr.first == N / 2 && curr.second == N / 2) {
      display_path(path);
      return;
   }
   for (int i = 0; i < 4; ++i) {
      int n = maze[curr.first][curr.second];
      int x = curr.first + dir_row[i]*n;
      int y = curr.second + dir_col[i]*n;
      pair<int, int> next = make_pair(x, y);
      if (is_ok(visited, next)) {
         visited.insert(next);
         path.push_back(next);
         solve(maze, path, visited, next);
         path.pop_back();
         visited.erase(next);
      }
   }
}
void search_path(int maze[N][N]) {
   list<pair<int, int> > path;
   set<pair<int, int> > visited;
   for (int i = 0; i < 4; ++i) {
      int x = row[i];
      int y = col[i];
      pair<int, int> pt = make_pair(x, y);
      visited.insert(pt);
      path.push_back(pt);
      solve(maze, path, visited, pt);
      path.pop_back();
      visited.erase(pt);
   }
}
int main() {
   int maze[N][N] = {
      {3, 4, 4, 4, 7, 3, 4, 6, 3},
      {6, 7, 5, 6, 6, 2, 6, 6, 2},
      {3, 3, 4, 3, 2, 5, 4, 7, 2},
      {6, 5, 5, 1, 2, 3, 6, 5, 6},
      {3, 3, 4, 3, 0, 1, 4, 3, 4},
      {3, 5, 4, 3, 2, 1, 3, 3, 5},
      {3, 5, 4, 3, 2, 6, 4, 4, 3},
      {3, 5, 1, 3, 7, 5, 3, 6, 3},
      {6, 2, 4, 3, 4, 5, 4, 5, 1}
   };
   search_path(maze);
}

入力

{{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}}

出力

(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(5, 1)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(8, 8)->(7, 8)->(4, 8)->(4, 4)->MIDDLE