Javaで次の問題を計算する方法を誰でも教えてくれます。有効な数字は 0 から 9 までの任意の数字で、# または * を除く 10 桁の長さで、チェスの駒が電話のキーパッドを移動中にトレースできる可能性のある有効な数字の数。ここでキングがいるとします。キングは実際のゲームと同じように、どの方向にも移動できますが、一度に 1 つのセルしか移動できません。
したがって、キーパッドは次のようになります。
1 2 3
4 5 6
7 8 9
* 0 #
そのため、ピースは毎回 10 回移動し、それによって作成されたそれぞれの固有の数字は有効な数字です。作品は最初の開始位置から旅を始めます。
更新: ピースは 1 つの場所に移動または滞在することができ (移動または滞在の両方が移動としてカウントされます)、セルを再訪することもできます (それぞれの移動権内で許可されている場合)。たとえば、キングが位置 1 から移動した場合、有効な数字を作成するための 3 つの有効な 10 回の移動パスは、1236547890 または 1111111111 または 1212121212 になります。
以下は、テスト用の 4 つのセルのみを含む 4 つのセルの正方形パッドの小さなバージョンのコードです。
public class King
{
private static final Integer[] ALLOWED_FROM_1 = {2, 3, 4};
private static final Integer[] ALLOWED_FROM_2 = {1, 3, 4};
private static final Integer[] ALLOWED_FROM_3 = {1, 2, 4};
private static final Integer[] ALLOWED_FROM_4 = {1, 2, 3};
List<Integer> visited;
public King()
{
this.visited = new ArrayList<Integer>();
}
public List<Integer> get_destinations(int currentPos, int noOfMoves)
{
if (noOfMoves == 0)
{
visited.add(currentPos);
return visited;
}
else
{
List<Integer> possibleMoves = getPossibleMoves(currentPos);
for (int i = 0; i < possibleMoves.size(); i++)
{
visited.add(possibleMoves.get(i));
get_destinations(possibleMoves.get(i), noOfMoves - 1);
}
return visited;
}
}
private List<Integer> getPossibleMoves(int currentPos)
{
List<Integer> possibleMoves = new ArrayList<Integer>();
switch (currentPos)
{
case 1 : possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_1));
break;
case 2: possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_2));
break;
case 3 : possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_3));
break;
case 4 : possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_4));
}
return possibleMoves;
}
}
上記のコードは、多くの異なる順列が欠落している部分的な回答のみを生成します。主な問題は、すべての順列を生成することをどのように正確に保証できるか、および上記のコードで正確にどの時点で (4 回の移動後に) 保存して後で取得する必要がある 4 桁の数字に到達するかです。また、 1234 1234 などの同じシーケンスの再訪を避けるにはどうすればよいので、基本的に最適化して、同じパスシーケンス/有効な番号が生成されないようにします。
すべての助けに感謝します。