picture of map. 我正在编写一个代码，使自己的网格充满点和1，其中1代表可获取的位置，而点代表可移动的位置。程序每次移动一个点，边界就会立即关闭。该程序应该找出提供最大战利品的最佳途径。我知道我必须为此使用递归，因为那是该项目的主题，但是我不确定如何完全实现它。
这是针对Java的，我尝试这样做以找出每条路径，但我不知道如何找到最佳路径。
public static int bestMoves(char[][] coordinates, int movesPossible, int playerX, int playerY, int mapSize, boolean[][] visited){
char[][] mapCopy = new char[mapSize][mapSize];
boolean[][] visitedCopy = new boolean[mapSize][mapSize];
for (int i = 0; i < mapSize; i++){
for (int j = 0; j < mapSize; j++){
mapCopy[i][j] = coordinates[i][j];
}
}
for (int i = 0; i < mapSize; i++){
for (int j = 0; j < mapSize; j++){
visitedCopy[i][j] = visited[i][j];
}
}
if (movesPossible > 0){
if (playerX - 1 >=0 && !visited[playerY][playerX-1]){
visitedCopy[playerX-1][playerY] = true;
if (coordinates[playerY][playerX-1] == '1'){
return 1 + bestMoves(mapCopy, movesPossible-1, playerX-1, playerY, mapSize-1,visited);
}else{
return bestMoves(mapCopy, movesPossible-1, playerX-1, playerY, mapSize-1,visited);
}
}
if (playerY - 1 >=0 && !visited[playerY-1][playerX]){
visitedCopy[playerY-1][playerX] = true;
if (coordinates[playerY-1][playerX] == '1'){
return 1 + bestMoves(mapCopy, movesPossible-1, playerX, playerY-1, mapSize-1,visited);
}else{
return bestMoves(mapCopy, movesPossible-1, playerX, playerY-1, mapSize-1,visited);
}
}
else if (playerY + 1 >= mapSize && !visited[playerY-1][playerX]){
visitedCopy[playerY][playerX] = true;
if (coordinates[playerY+1][playerX] == '1'){
return 1 + bestMoves(mapCopy, movesPossible-1, playerX, playerY+1, mapSize-1,visited);
}else{
return bestMoves(mapCopy, movesPossible-1, playerX, playerY+1, mapSize-1,visited);
}
}
else if (playerX + 1 >= mapSize && !visited[playerY-1][playerX]){
visitedCopy[playerY][playerX] = true;
if (coordinates[playerY+1][playerX] == '1'){
return 1 + bestMoves(mapCopy, movesPossible-1, playerX+1, playerY, mapSize-1,visited);
}else{
return bestMoves(mapCopy, movesPossible-1, playerX+1, playerY, mapSize-1,visited);
}
}else{
return 0;
}
}else{
return 0;
}
我主要在外部调用此函数，但它始终只返回数字1而不是最佳路径。这是正在使用的地图
1。 。 。 。 。 。 。 。 。 。
。 。 。 。 。 。 。 。 。 。 。
。 。 。 。 。 。 。 。 1。 。
。 。 。 。 1。 。 。 。 。 。
。 。 1P。 1 1 1。 。 。
。 。 1 1 。 。 。 。 。 。
。 。 。 1。 。 1。 。 。 。
。 。 。 。 。 。 。 。 。 。 1个
。 1 1 1。 。 。 。 。 。 。
。 。 1。 。 。 。 。 。 。 。
。 。 。 。 。 。 。 。 1 1 1
p是原始位置
最佳答案
我想到的一种可能的解决方案与MiniMax算法有关。在通常适合两个基于玩家的零和游戏的算法中，您将创建一棵游戏树并评估可能的位置，直到最大深度。当然，这可以进行调整，我们这里只有一名玩家，因此可以为每个外向移动（如果需要，向左，向右，向上，向下，对角线）创建游戏树，并使用对每个得分都更高的函数进行评估收集点。如果板上没有更多的点，则不会创建更多的出局头寸。最后，选择得分最高的那条路。
如果深度足够好，则应始终尽力而为。
当然，如果电路板变大，可能会有更好的算法。但是，由于董事会的一举一动都在迅速缩小，因此应该能够生成所有职位。