C++のMazeIII

空のスペースと壁のある迷路があり、その迷路の中にボールもあるとします。ボールは、上（u）、下（d）、左（l）、または右（r）の方向に転がることで空きスペースを通過できますが、壁にぶつかるまで転がり続けます。ボールが止まると、次の方向を選ぶことができます。その迷路にも1つの穴があります。ボールが穴に転がると、ボールは穴に落ちます。

したがって、ボールの位置、穴の位置、迷路がある場合、最短距離を移動することでボールがどのように穴に落ちるかを調べる必要があります。ここで、距離は、ボールがスタート（除外）からホール（含まれる）まで移動した空きスペースの数によって定義されます。

「u」、「d」、「l」、「r」を使用して移動方向を返します。いくつかの異なる最短の方法がある可能性があるため、出力は辞書式順序で最小の方法である必要があります。ボールが穴に到達できない場合は、「不可能」と表示します。

ここでは、迷路はバイナリ行列で表されます。 1は壁を意味し、0は空きスペースを意味します。ボールと穴の座標は、行と列のインデックスで表されます。

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

次に、出力は左に移動してから上に移動すると「lul」になり、別の結果は「ul」になります。上から左に移動します。どちらも長さ6ですが、辞書式順序で「lul」より小さくはありません。

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

• データと呼ばれる1つのデータ型を定義します。これには距離、文字列d、座標x、yが必要です。

• サイズの配列ディレクトリを定義します：4 x 2：={{1、0}、{0、-1}、{0、1}、{-1、0}}

• サイズが最初の配列を定義します：4：={'d'、'l'、'r'、'u'}

• 関数ok（）を定義します。これには、x1、y1、x2、y2、

  が必要です。

• x1がx2と同じで、y1がy2と同じである場合、trueを返します

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

• n：=迷路の行サイズ

• m：=（nがゼロ以外の場合、迷路の列サイズ、それ以外の場合は0）

• 1つの優先キューpqを定義する

• （0、ball [0]、ball [1]、 ""）を含む新しいデータをpqに挿入します

• サイズnxm

  の訪問した2D配列を1つ定義します。

• （pqが空ではない）間、-

  • curr：=pqの最上位要素

  • x：=curr.x

  • y：=curr.y

  • dist：=curr.dist

  • d：=curr.d

  • ok（x、y、hole [0]、hole [1]）の場合、-

    • dを返す

  • 訪問済み[x、y]：=true

  • pqから要素を削除する

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

    • nx：=x、ny：=y

    • tempDist：=0

    • 一方、nx + dir [k、0]=0およびny+dir [k、1]=0およびmaze[nx + dir [k、0]、ny + dir [k、1]]は0、do-

      • nx：=nx + dir [k、0]

      • ny：=ny + dir [k、1]

      • （tempDistを1増やします）

      • ok（nx、ny、hole [0]、hole [1]）の場合、-

        • ループから出てきます

    • visited [nx、ny]がゼロの場合、-

      • 新しいデータ（dist + tempDist、nx、ny、d + dirst [k]）をpqに挿入します

  • 「不可能」を返す

例

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

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char dirst[4] = {'d', 'l', 'r', 'u'};
class Solution {
public:
   struct Data {
      int dist;
      string d;
      int x, y;
      Data(int a, int b, int c, string s) {
         d = s;
         dist = a;
         x = b;
         y = c;
      }
   };
   struct Comparator {
      bool operator()(Data a, Data b) {
         return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d);
      }
   };
   bool ok(int x1, int y1, int x2, int y2) { return x1 == x2 && y1 == y2; }
   string findShortestWay(vector<vector<int>> &maze, vector<int>&ball,
      vector<int> &hole) {
         int n = maze.size();
         int m = n ? maze[0].size() : 0;
         priority_queue<vector<Data>, vector<Data>, Comparator> pq;
         pq.push(Data(0, ball[0], ball[1], ""));
         vector<vector<bool>> visited(n, vector<bool>(m));
         while (!pq.empty()) {
            Data curr = pq.top();
            int x = curr.x;
            int y = curr.y;
            int dist = curr.dist;
            string d = curr.d;
            if (ok(x, y, hole[0], hole[1])) {
               return d;
            }
            visited[x][y] = true;
            pq.pop();
            for (int k = 0; k < 4; k++) {
               int nx = x;
               int ny = y;
               int tempDist = 0;
               while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && ny + dir[k][1] < m && ny + dir[k][1] >= 0 && !maze[nx + dir[k][0]][ny + dir[k][1]]) {
                  nx += dir[k][0];
                  ny += dir[k][1];
                  tempDist++;
                  if (ok(nx, ny, hole[0], hole[1]))
                     break;
               }
               if (!visited[nx][ny]) {
                  pq.push(Data(dist + tempDist, nx, ny, d + dirst[k]));
               }
            }
         }
         return "impossible";
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {
      {0, 0, 0, 0, 0},
      {1, 1, 0, 0, 1},
      {0, 0, 0, 0, 0},
      {0, 1, 0, 0, 1},
      {0, 1, 0, 0, 0}};
   vector<int> v1 = {4, 3}, v2 = {0, 1};
   cout << (ob.findShortestWay(v, v1, v2));
}

入力

vector<vector<int>> v = {{0, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 0}};
vector<int> v1 = {4, 3}, v2 = {0, 1};

出力

lul