C++でグリッド内の指定方向に実行可能な移動回数をカウントする方法

サイズ n × m のグリッドと、開始座標 (x, y) を表す変数が与えられます。さらに、グリッド内を移動するために使用できるステップのペア（例：(1,1)、(2,2) など）も与えられます。各ペアは、x 軸と y 軸方向に進む単位移動量を表します。ゴールは、境界 [1, n] × [1, m] の範囲内でグリッド内を移動できる合計ステップ数を求めることです。

たとえば、n = 5、m = 4、現在位置が (2, 2)、選択したステップが (1, -1) の場合を考えてみましょう。このステップを 1 回適用すると (3, 1) に移動できますが、もう 1 回適用すると (4, -1) となり、-1 は範囲外であるため無効な移動です。

入力例と出力例

入力： A = 3、B = 4、x = 1、y = 1、moves = { 1, 1 }, { 0, -1 }

出力： グリッド内の指定方向に可能な移動回数 ― 4

説明：

move {1, 1} を選択 → (2, 2) → (3, 3)：2 ステップ
move {0, -1} を選択 → (3, 2) → (3, 1)：2 ステップ
合計 4 ステップ。

入力： A = 4、B = 4、x = 2、y = 2、moves = { 2, 1 }, { -2, -3 }

出力： グリッド内の指定方向に可能な移動回数 ― 1

説明：

move {2, 1} を選択 → (4, 3)：1 ステップ
move {-2, -3} を選択 → (2, 0)：範囲外のため無効
合計 1 ステップ。

プログラムで使用しているアプローチ

このアプローチでは、ステップを pair<int, int> として表すベクターを作成します。点 (x, y) から移動を開始し、ベクターからステップを 1 つ選んで、両方向（x 軸方向と y 軸方向）で移動できる回数の最小値を採用します。最小値を選ぶことで、より多くの移動を実行できます。特定の方向へ移動する場合、現在位置 x（または y）が n（または m）より大きければ、n（または m）に到達するまでの移動回数は (n − 現在位置) / x となり、小さければ 1 に到達するまでの移動回数は (現在位置 − 1) / x となります。

• A × B のグリッドを表す変数 A、B と、開始点を表す x、y を用意します。
• 整数ペアのベクターとして移動（vector<pair<int, int>>）を受け取ります。
• 関数 possible_moves(int x, int y, int A, int B, vector<pair<int, int>> 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 < size までベクターを走査します。
• 現在の移動ペアから座標を temp_x = move[i].first、temp_y = move[i].second として取り出します。
• 関数 possible() を使って、可能な移動回数の最小値を変数 check とします。
• check の値を合計ステップ数の count に加算します。
• check を選んだので、x と y を check 分だけ更新します。
• 最終的に、グリッド内の指定方向に可能な合計移動回数が得られます。
• 結果として count を返します。

コード例

#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<<"グリッド内の指定方向に可能な移動回数: "<<possible_moves(x, y, A, B, move, size);
    return 0;
}

出力

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

グリッド内の指定方向に可能な移動回数: 3

このサンプルでは、開始位置 (3, 3) から move {2, -1} を適用しても x 座標がすでに上限 A = 3 に達しているため 0 ステップ、次に move {0, 1} によって y 座標が上限 B = 6 まで 3 ステップ進み、最後の move {1, -2} は再び x 座標が上限に達しているため 0 ステップとなります。その結果、合計 3 ステップという答えが得られます。