1

Intento resolver un desafío de la página Hackerrank en el que se solicita determinar la cantidad de cuadros que una reina (ajedrez) puede atacar en un tablero de n * n lados con k obstáculos.

Mi solución aprueba la mayoría de los casos de prueba pero, al final muestra "Terminated due to timeout"

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

//Desde aquí es código propio
private static int n;
private static int k;
private static int r_q;
private static int c_q;
private static int[][] obstacles;

static int queensAttack() {
    int result = 0;
    int[][] directions = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
    for (int i = 0; i < 8; i++) {
                result += checkLine(directions[i][0], directions[i][1]);
    }
    return result;
}

private static int checkLine(int dirR, int dirC){
    int result = 0;
    int TmpR_q = r_q;
    int TmpC_q = c_q;
        for (int i = 0; i < n; i++) {
            TmpR_q += dirR;
            TmpC_q += dirC;
            if (TmpR_q <= n && TmpR_q > 0 && TmpC_q <= n && TmpC_q > 0){
                for (int j = 0; j < k; j++) {
                 if (TmpR_q == obstacles[j][0] && TmpC_q == obstacles[j][1]) {
                    return result;
                }
            }
            result++;
            }
        }
    return result;
}
//Hasta aquí es código proprio

private static final Scanner scanner = new Scanner(System.in);

//Modificaciones mínimas desde aquí
public static void main(String[] args) throws IOException {
    BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    String[] nk = scanner.nextLine().split(" ");

    n = Integer.parseInt(nk[0]);

    k = Integer.parseInt(nk[1]);

    String[] r_qC_q = scanner.nextLine().split(" ");

    r_q = Integer.parseInt(r_qC_q[0]);

    c_q = Integer.parseInt(r_qC_q[1]);

    obstacles = new int[k][2];

    for (int i = 0; i < k; i++) {
        String[] obstaclesRowItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int j = 0; j < 2; j++) {
            int obstaclesItem = Integer.parseInt(obstaclesRowItems[j]);
            obstacles[i][j] = obstaclesItem;
        }
    }

    int result = queensAttack();

    bufferedWriter.write(String.valueOf(result));
    bufferedWriter.newLine();

    bufferedWriter.close();

    scanner.close();
}
}

Lo que requiero es ayuda para optimizar el código y poder ejecutar los casos de pruebas en el tiempo determinado.

De antemano, gracias.

2
  • Lo primero que deberías hacer es renombrar las variables: líneas como if (TmpR_q <= n && TmpR_q > 0 && TmpC_q <= n && TmpC_q > 0){ hacen que deje de seguir leyendo porque es un esfuerzo enorme entender qué intentas hacer Commented el 31 dic. 2018 a las 11:04
  • Gracias por el comentario, lo tendré en cuenta. Saludos Commented el 2 ene. 2019 a las 10:09

1 respuesta 1

0

Tu programa básicamente guarda todos los posibles obstáculos en una lista, y para cada posible cuadro i,j de la diagonal itera sobre esa lista para ver si encuentra un obstáculo. Eso es muy ineficiente.

La primera aproximación es poner los obstáculos en un array bidimensional para hacer la búsqueda directa: si estás evaluando la casilla i,j vas a obstaculos[i][j] y miras si hay un elemento. Así evitas repasar la lista de obstáculos cada vez.

En todo caso, yo cambiaría la forma de proceder. Al fin y al cabo, si la posición de tu reina es (i, j) y un obstáculo está en (io, jo), entonces:

  • El obstáculo solo te importa
    • si i = io (misma fila), o
    • si j = jo (misma columna), o
    • si abs(j - jo) = abs(i - io) (misma diagonal).

Y en los tres casos, obtener la distancia del obstáculo a la reina es trivial.

Así que para cada fila, columna y diagonal puedes identificar fácilmente cuál es el obstáculo más cercano, y a qué distancia está. En cada fila, columna y diagonal, el número de casillas cubiertas será la distancia al obstáculo más cercano menos uno.

1
  • Sobre la primer propuesta (búsqueda directa), seguía obteniendo el error. Cambié la forma de proceder basándome en la segunda propuesta. La solución fue filtrar los obstáculos desde la lectura, crear una Lista con la cantidad de casillas entre la reina y los límites del tablero en las 8 direcciones; iterar la lista de obstáculos obteniendo la diferencia entre este y la reina, si la distancia era menor a la guardada (según la dirección) se sustituía en la lista, al final se suma la lista. Funcionó muy bien aunque no pasó una prueba (resultado incorrecto). Muchas gracias por el apoyo. Commented el 2 ene. 2019 a las 10:30

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.