問題 CCHESS を実行しています。問題へのリンク ( http://www.spoj.pl/problems/CCHESS/ ) を参照してください。
質問は次のとおりです。
ローマの国では、チェスは王室のゲームです。すべての動きのために、プレーヤーはユルグ皇帝にいくらかのお金を与えなければなりませんでした。LGMs またはリトル グリーン メンは、チェスの非常に優れたプレーヤーです。しかし、チェスは高価なゲームであるため、それが王室である理由です。彼らは、ナイトをあるポジションから別のポジションに移動するために支払わなければならない最低額を見つけるのを手伝ってくれるように頼みました。目的地に到達するために任意の数のステップを使用できます。
制約:
チェスのサイズは 8X8 で、インデックスは左下のセル (0, 0) です。
ナイトは標準的な方法、つまり 2 列 1 列または 1 列 2 列のみで移動します。
ステップで騎士が (a, b) から (c, d) に移動した場合、LGM は a*c + b*d ドルをユルグ皇帝に支払わなければなりませんでした。
0 ≤ a, b, c, d ≤ 7
入力
100 ～ 150 のテスト ケースがあります。各テスト ケースは、スペースで区切られた 4 つの整数で構成されます。最初の 2 つの数字 a、b は Knight の開始位置であり、次の 2 つの c、d は Knight の目的地です。ファイルの終わりまで読み取ります。出力
テストケースごとに、彼らが支払わなければならなかった最低金額を別々の行に出力してください。目的地に到達できない場合は、-1 を出力します。
例
入力：
2 5 5 2
4 7 3 2
1 2 3 4
出力：
42 78 18
テスト ケース #1 の説明: 2 5 5 2
ナイトを(2,5)から(5,2)に移動
in minimum cost, one of the path is
(2, 5) -> (3, 3) ->(5, 2)
支払われたドル:
(2, 5) = 0
(2, 5) -> (3, 3) = 0 + (2*3 + 5*3) = 21
(3, 3) -> (5, 2) = 21 + (3*5 + 3*2) = 42
無限の彼方へ...
私はブルートフォースを使用してこの問題を解決しました。つまり、可能なすべてのパスを再帰的にチェックしましたが、直接的なアプローチを見つけるにはどこかが欠けていると思います。どんな助けでも大歓迎です。