C++でマトリックス上の2点間の単一移動方向を判定する方法

問題概要

この問題では、2つの点 (x1, y1) と (x2, y2) を表す4つの整数値 x1、y1、x2、y2 が与えられます。求めるのは、始点 (x1, y1) から終点 (x2, y2) へたった1回の移動で到達するための方向です。マトリックス上での移動に使える方向は1つだけで、答えは「Left（左）」「Right（右）」「Up（上）」「Down（下）」のいずれかの形式で返します。どの一方向でも到達できない場合は -1 を返し、「不可能」であることを示します。

入力例

x1 = 2, y1 = 1, x2 = 5, y2 = 1

出力例

Down

解き方のアプローチ

この問題のポイントは、「始点から終点へ1回の直線移動で到達するには、x座標（x1とx2）またはy座標（y1とy2）のどちらか一方が必ず等しくなる」という性質を利用することです。片方の座標だけが変化する場合、その変化の向きから移動方向を一意に決定できます。

条件を整理すると、以下の4つのケースに分類されます。

ケース1: x1 == x2 かつ y1 > y2 の場合 → 方向 : Left（左）
ケース2: x1 == x2 かつ y2 > y1 の場合 → 方向 : Right（右）
ケース3: y1 == y2 かつ x1 > x2 の場合 → 方向 : Up（上）
ケース4: y1 == y2 かつ x2 > x1 の場合 → 方向 : Down（下）

反対に、x座標とy座標の両方が異なる場合は斜め移動が必要になるため、1回の移動では到達できず「Not Possible（不可能）」と判定されます。

C++による実装例

以下は、このソリューションの動作を示すC++プログラムです。

#include <iostream>
using namespace std;

void findSingleMovement(int x1, int y1, int x2, int y2) {
    if (x1 == x2 && y1 < y2)
        cout<<"Right";
    else if (x1 == x2 && y1 > y2)
        cout<<"Left";
    else if (y1 == y2 && x1 < x2)
        cout<<"Down";
    else if (y1 == y2 && x1 > x2)
        cout<<"Up";
    else
        cout<<"Not Possible";
}

int main() {
    int x1, x2, y1, y2;
    x1 = 2; y1 = 1;
    x2 = 5; y2 = 1;
    cout<<"The direction of movement is ";
    findSingleMovement(x1, y1, x2, y2);
    return 0;
}

実行結果

The direction of movement is Down

まとめ

本アルゴリズムは座標の比較だけで方向を判定できるため、時間計算量・空間計算量はともに O(1) と非常に効率的です。2点が同じ行または同じ列上にあるかを確認するだけでよいので、実装もシンプルで実用的です。