【アルゴリズム】格子点の問題

Question

前提・実現したいこと

ロジック力強化のためにアルゴリズムの勉強をしているのですが、
以下の問題のアルゴリズムをどうすればよいかわかりません。

問題文

あなたは現在 xy 平面上の格子点 (X1,Y1) にいます。
あなたは、格子点 (X2,Y2) に到達したいです。 
あなたは、以下のような移動を行うことができます。

・今いる点の x 座標が偶数のとき、 y 軸の正の方向に移動する。
・今いる点の x 座標が奇数のとき、 y 軸の負の方向に移動する。
・今いる点の y 座標が偶数のとき、 x 軸の正の方向に移動する。
・今いる点の y 座標が奇数のとき、 x 軸の負の方向に移動する。

これらの移動を繰り返すことで格子点 (X2,Y2) に到達するために必要な総移動距離の最小値を求めてください。

自分の書いたソースコード

以下、現状のソースコードになります。
到達目標座標の偶奇が考慮できていないため、無限ループに入ってしまいます。

import java.util.*;

public class Main {

	/* 移動距離カウント用 */
	static int c = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		/* 今いる座標 */
		int x = sc.nextInt();
		int y = sc.nextInt();

		/* 到達目標座標 */
		final int x2 = sc.nextInt();
		final int y2 = sc.nextInt();

		int xyc;
		int yxc;

		int x1 = x;
		int y1 = y;

                /* y→xの順 */
		while (true) {
			if (x1 % 2 == 0) { /* 今いるx座標が偶数 */
				y1 += moveCoordinate(y1, y2, "even");
			} else if (Math.abs(x1 % 2) == 1) { /* 今いるx座標が奇数 */
				y1 += moveCoordinate(y1, y2, "odd");
			}

			System.out.println(x1 + " " + y1);

			if (x1 == x2 && y1 == y2) {
				break;
			}

			if (y1 % 2 == 0) { /* 今いるy座標が偶数 */
				x1 += moveCoordinate(x1, x2, "even");
			} else if (Math.abs(y1 % 2) == 1) { /* 今いるy座標が奇数 */
				x1 += moveCoordinate(x1, x2, "odd");
			}

			System.out.println(x1 + " " + y1);

			if (x1 == x2 && y1 == y2) {
				break;
			}
		}
		//System.out.println(c);
		yxc = c;

		c = 0;
		x1 = x;
		y1 = y;

		System.out.println();
                /* x→yの順 */
		while (true) {
			if (y1 % 2 == 0) { /* 今いるy座標が偶数 */
				x1 += moveCoordinate(x1, x2, "even");
			} else if (Math.abs(y1 % 2) == 1) { /* 今いるy座標が奇数 */
				x1 += moveCoordinate(x1, x2, "odd");
			}

			System.out.println(x1 + " " + y1);

			if (x1 == x2 && y1 == y2) {
				break;
			}

			if (x1 % 2 == 0) { /* 今いるx座標が偶数 */
				y1 += moveCoordinate(y1, y2, "even");
			} else if (Math.abs(x1 % 2) == 1) { /* 今いるx座標が奇数 */
				y1 += moveCoordinate(y1, y2, "odd");
			}

			System.out.println(x1 + " " + y1);

			if (x1 == x2 && y1 == y2) {
				break;
			}
		}
		//System.out.println(c);
		xyc = c;

		if (xyc < yxc) { /* x軸→y軸の順 */
			System.out.println(xyc);
		} else { /* y軸→x軸の順 */
			System.out.println(yxc);
		}

	}

	public static int moveCoordinate(int a, int b, String evenness) {
		if (evenness == "even") { // 正方向へ移動
			if (a < b) {
				c += Math.abs(b - a);
				return Math.abs(b - a);
			} else /* if (a >= b) */{
				c++;
				return 1;

			}

		} else if (evenness == "odd") { // 負方向へ移動
			if (a > b) {
				c += Math.abs(a - b);
				return -(Math.abs(a - b));
			} else /* if (a <= b) */{
				c++;
				return -1;
			}
		}
		return 0;
	}
}

補足情報

入力は以下の形式で標準入力から与えられる。

X1 Y1
X2 Y2

入力例1

0 1
5 1

出力例1

7

(0,1) → (0,2) → (5,2) → (5,1) と移動すると総移動距離は 7 となり、これは最小です。

入力例2

100000000 100000000
-100000000 -100000000

出力例2

400000004

(100000000,100000000) → (100000001,100000000) → (100000001,−100000001) → (−100000000,−100000001) → (−100000000,−100000000) と移動すると総移動距離は 400000004 となり、これは最小です。

入力例3

3 -1
4 8

出力例3

12

Comments

[fana]

https://teratail.com/questions/306606#reply-430054
同じ？

[Sh1xy0u]

同じですが、考え方を聞いているのではありません。
上記コードにどういう処理が足せばいいのかを質問させていただいております。

[m.ts10806]

同じ人？

[fana]

リンク先の回答内に

> 到達目標座標の偶奇が考慮できていないため

に対して，偶奇を考慮するならこういう処理かな，という話が書いてあるつもりなのですが，これでは「どういう処理を足せばいいか」という話には該当しませんか？

欲しいのは　処理の内容の話　なのではなくて，あなたのコードを土台にして完成させた具体的なコード　である，という話ですか？

[fana]

あなたの現状態に基づいての話を希望するのであれば，現状の説明をした方が良いのではないでしょうか．
あなたが考えたアルゴリズムはどういうもので，現コードのどの部分がそのアルゴリズムのどこに対応してるのか，等．

Answer 1

とりあえず，「質問への追記・修正の依頼」欄で示した
https://teratail.com/questions/306606#reply-430054
にある回答内容のアイデアの実装を示す．
（言語はC++になっているが，疑似コードとして読めるだろう）

※XDir_then_YDirとはXとYを逆順に扱わねばならないパターンがあり得るのかどうかは不明．
（とりあえず質問文に提示されている３つの例については正答が得られているが，果たして？）
必要ならば，逆順の処理も行って，２つのうち小さい側を答えとすればよい．

//引数が偶数のとき1, 奇数のとき-1を返す
inline int MovableDir( int P ){ return ( (P & 0x1) ? -1 : 1 );  }

//
unsigned int XDir_then_YDir( int X1,int Y1, int X2,int Y2 )
{
    unsigned int Count = 0;
    
    int dx = X2 - X1;
    if( dx != 0 )
    {//現在位置から，行きたいX方向にいけるのかを調べる．
        //無理な場合は，行きたいX方向にいけるようにするために，まずY方向に一歩動く．
        if( MovableDir(Y1) * dx < 0 )
        {   Y1 += MovableDir(X1);   Count=1;    }
    }
    
    //X方向に関して，ダイレクトにX=X2に移動してよいのかどうか調べる．
    int dy = Y2 - Y1;
    if( MovableDir(X2) * dy >= 0 )
    {//X=X2から直接Y=Y2に向かえる場合
        //X=X2に移動し，あとはY=Y2にそのまま移動すればよい．
        return Count + abs(dx) + abs(dy);
    }
    else
    {//ダイレクトにX2に移動しても所望のY方向に移動できない場合
        //まず，X方向に関して，現在値から見て，X2の一歩手前か，あるいは一歩先まで移動する
        //そうすれば，Y = Y2 まで移動できる．
        //この時点で，ゴールは隣接しているから，X方向に一歩動けばいい．
        Count += abs(dx) + abs(dy);
        if( MovableDir(Y2) * dx < 0 ){  Count += 2; }
        return Count;
    }
}

int main(void)
{
    std::cout << XDir_then_YDir( 0,1, 5,1 ) << std::endl;
    std::cout << XDir_then_YDir( 100000000,100000000, -100000000,-100000000 ) << std::endl;
    std::cout << XDir_then_YDir( 3,-1, 4,8 ) << std::endl;
    return 0;
}

Comments

[fana]

※　XDir_then_YDirの中身はもっと短くまとめることはできるだろうが，ここでは説明が目的なので，愚直な形の実装を示した．