Tengo un juego de "mini ajedrez", donde el caballo puede moverse igual que el juego de ajedrez normal, necesito encontrar el camino más corto desde el caballo H hasta el rey K.

Necesito escribir una función recursiva . la firma de la función debe ser public static int minPath(char[][] minChess,int i,int j)

En mi solución, marqué cada lugar donde el caballo pisó con X y, por lo tanto, el caballo no puede pisar dos veces en el mismo lugar y creo que esta es la causa de mi solución incorrecta.

Aquí está mi código:

    public static void main(String[] args) {
        char[][] minChess={{'0','0','K','0'},
                           {'0','0','0','0'},
                           {'0','0','0','0'},
                           {'H','0','0','0'}};

        System.out.println(minPath(minChess,3,0));
    }

    public static int minPath(char[][] minChess,int i,int j)
    {
        return minPath(minChess,i,j,0);
    }
    
    public static int minPath(char[][] minChess,int i,int j,int count)
    {
        if(!isValidLocation(minChess,i,j))
            return Integer.MAX_VALUE;
        
        if(minChess[i][j]=='K'){
            return count;
        }
        if(minChess[i][j]=='X'){
            return Integer.MAX_VALUE;
        }
            
        minChess[i][j]='X';
       //all direction the hourse can move
        int dir1=minPath(minChess,i-1,j-2,count+1);     
        int dir2=minPath(minChess,i-2,j-1,count+1); 
        int dir3=minPath(minChess,i-2,j+1,count+1);     
        int dir4=minPath(minChess,i-1,j+2,count+1);     
        int dir5=minPath(minChess,i+1,j+2,count+1);     
        int dir6=minPath(minChess,i+2,j+1,count+1);         
        int dir7=minPath(minChess,i+1,j-2,count+1);     
        int dir8=minPath(minChess,i+2,j-1,count+1);
        
        
        return Math.min(dir1,Math.min(dir2, Math.min(dir3, Math.min(dir4, Math.min(dir5, Math.min(dir6, Math.min(dir7, dir8)))))));
        
    }
    public static boolean isValidLocation(char[][] a,int i,int j)
    {
        return i>=0&&j>=0&&i<a.length&&j<a[0].length;
    }

La salida es: 5 pero debería ser 3.

No puedo ver cómo completar la solución

-3
spez 25 jun. 2020 a las 10:08

2 respuestas

La mejor respuesta

Agrega la línea

MinChess [i] [j] = ״ 0 ״

Debajo de las llamadas recursivas.

Eso limpiará las celdas marcadas

1
Nehorai 26 jun. 2020 a las 05:48

Este método calcula todas las distancias más cortas para el tamaño del tablero (alto x ancho) que comienza con (startX, startY)

static final int[][] DIRECTIONS = {
    {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
    {1, -2}, {1, 2}, {2, -1}, {2, 1}};

static int[][] shortestDistances(int height, int width, int startX, int startY) {
    int[][] board = new int[height][width];
    for (int[] row : board)
        Arrays.fill(row, Integer.MAX_VALUE);
    new Object() {
        void set(int x, int y, int distance) {
            if (x < 0 || x >= height || y < 0 || y >= width)
                return;
            if (distance >= board[x][y])
                return;
            board[x][y] = distance;
            for (int[] direction : DIRECTIONS)
                set(x + direction[0], y + direction[1], distance + 1);
        }
    }.set(startX, startY, 0);
    return board;
}

Una muestra de ejecución (tablero de 4 x 4, comienza con (3, 0))

int[][] distances = shortestDistances(4, 4, 3, 0);
for (int[] row : distances)
    System.out.println(Arrays.toString(row));

Resultado

[5, 2, 3, 2]
[2, 1, 4, 3]
[3, 4, 1, 2]
[0, 3, 2, 5]

Si el rey estuviera en (0, 2), la distancia sería 3.

0
saka1029 25 jun. 2020 a las 11:25