C++のグリッドで指定された方向に可能な移動をカウントします

サイズnxmのグリッドと開始点x、yを表す2つの変数nとmです。

また、移動（（1,1）、（2,2））などとしてグリッド内を移動するために実行できるステップ/移動のペアも指定されます。移動の各ペアは、x、y軸で実行されるステップの単位を表します。目標は、境界[1、n] X [1、m]内のグリッド内をトラバースするために実行できる合計ステップを見つけることです。nが5、mが4、現在の位置が2、2で、選択されたステップが（ 1、-1）次に、このステップを1回実行すると、（3,1）になります。このステップを再度実行すると、（4、-1）になります。これは、-1が範囲外であるため無効です。

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

入力 − A =3、B =4、x =1、y =1;移動={1、1}、{0、-1}

出力 −グリッド内の特定の方向への可能な移動の数は− 4

説明 −

Choosing move {1,1} = → (2,2) → (3,3) - 3 steps
Choosing move {0,-1} = → (3,2) → (3,1) - 2 steps
Total 4 steps.

入力 − A =4、B =4、x =2、y =2;移動={2、1}、{-2、-3}

出力 −グリッド内の特定の方向への可能な移動の数は− 1

説明

Choosing move {2,1} = → (4,3) - 1 step1
Choosing move {-2,-3} = → (2,0) X out of bound
Total 1 step

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

このアプローチでは、ステップをpair として表すベクトルを作成します。ポイントx、yからトラバースを開始します。ベクトルからステップを選択し、両方向（x軸とy軸）で取得される値の最小値を選択します。選択された最小値により、より多くの動きが可能になります。特定の方向に移動するには、cur位置x（またはy）が> n（またはm）の場合、n（またはm）に到達するための移動回数は（n-cur位置）/xです。それより少ない場合、1に到達するまでの移動回数は（cur position-1）/xです。

• AXBグリッドを表すために変数A、Bを取り、開始点としてx、yを取ります。

• 整数ペアを含むベクトルを移動として取得します（ベクトル>）。

• 関数possible_moves（int x、int y、int A、int B、vector > move、int size）はすべての変数を取り、移動し、グリッド内の指定された方向に可能な移動の数を返します。

• 関数possible（int x、int temp_x、int A）は、座標の現在の位置をx、移動中の対応する座標値をtemp_x、その座標のグリッドの制限をAとします。

• ここで、temp_xが0の場合、INT_MAXを返して、戻り値を最大にします。

• temp_xが>0の場合、Aに到達するための移動は|になります。 A-x | / temp_x

• それ以外の場合、1つの動きに向かって移動します| x-1|/temp_x。

• 対応する計算された動きを返します。

• possible_moves（）内で、初期カウントを0とします。

• forループを使用してi=0からiまでベクトルをトラバースします。

• 現在の移動のペアから、temp_x =move[i].firstおよびtemp_y=move[i].secondとして座標を抽出します。

• 関数possible（）を使用して、可能な最小の動きとして変数チェックを行います。

• チェックの最小値が合計ステップ数に追加されます。

• チェックを選択したので、xとyをチェックで更新します。

• 最後に、グリッド内の特定の方向に可能な移動の総数を取得します

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int possible(int x, int temp_x, int A){
   if(temp_x == 0){
      return INT_MAX;
   }
   if (temp_x > 0){
      return abs((A - x) / temp_x);
   }
   else{
      return abs((x - 1) / temp_x);
   }
}
int possible_moves(int x, int y, int A, int B, vector<pair<int, int>> move, int size){
   int count = 0;
   for (int i = 0; i < size; i++){
      int temp_x = move[i].first;
      int temp_y = move[i].second;
      int check = min(possible(x, temp_x, A), possible(y, temp_y, B));
      count = count + check;
      x = x + check * temp_x;
      y = y + check * temp_y;
   }
   return count;
}
int main(){
   int A = 3, B = 6, x = 3, y = 3;
   vector<pair<int, int> > move = {
      { 2, -1 },
      { 0, 1 },
      { 1, -2 }
   };
   int size = move.size();
   cout<<"Count of possible moves in the given direction in a grid are: "<<possible_moves(x, y, A, B, move, size);
   return 0;
}

出力

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

Count of possible moves in the given direction in a grid are: 3