1

Necesito crear un "campo minado" en C compuesto por espacios vacíos, tesoros y minas dispuestos al azar.

Para asignarle una ubicación a cada mina y tesoro, primero uso dos arreglos: UbicacionObjetoX y UbicacionObjetoY, que son arreglos que incluyen a todos los objetos que no sean vacío (básicamente, la suma de las minas y los tesoros). Así, después imprimo el campo minado como una matriz que sustituye los espacios vacíos en las coordenadas de las minas y los tesoros por una letra T o M.

Sin embargo, cuando estoy asignándole ubicaciones a los objetos antes de asignárselas a los tesoros y minas, existe la posibilidad de que las ubicaciones se repitan. Por ejemplo, UbicacionObjetoX[4] y UbicacionObjetoY[4] sean iguales a UbicacionObjetoX[10] y UbicacionObjetoY[10]. Esto causará, hasta donde yo sé, que no se imprima nada en su lugar.

Mi objetivo no es que no se repitan las ubicaciones de los ejes X o Y de cada arreglo por separado, sino que no se repitan las ubicaciones de los ejes X e Y.

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <time.h>
main(){
        int i , j ;
        int Filas , Columnas ;
        int CantidadObjetos , CantidadTesoros , CantidadMinas ;
        Filas = 10 ;
        Columnas = 10 ;
        CantidadTesoros = 5 ;
        CantidadMinas = 10 ;
        CantidadObjetos = CantidadTesoros + CantidadMinas ; 
        int UbicacionObjetoX[CantidadObjetos] , UbicacionObjetoY[CantidadObjetos] ;
        int k ;     
        for(k=0;k<CantidadObjetos;k++){
            UbicacionObjetoX[k] = rand()%Filas ;
            UbicacionObjetoY[k] = rand()%Columnas ;
            printf( "%d. %d,%d \n" , k , UbicacionObjetoX[k] , UbicacionObjetoY[k] ) ;
        }
}
1
  • Por favor, aclara tu problema específico o proporciona detalles adicionales para resaltar exactamente lo que necesitas. Tal como está escrito, es difícil saber exactamente qué estás preguntando.
    – Comunidad Bot
    Commented el 7 ago. 2022 a las 8:53

1 respuesta 1

0

Parece que quieres crear unas cuantas (concretamente 15 en este ejemplo) parejas de puntos (X,Y), estando tanto X como Y entre 0 y 10, y sin que aparezcan pares (X,Y) repetidos entre los generados.

Hay dos formas de evitar que salgan repetidos, una fácil de programar (pero ineficiente) y otra más compleja y hasta retorcida, pero muy eficiente.

La fácil es:

  • Generas un par (X,Y)
  • Miras si ya estaba entre los generados, si ya estaba no lo cuentas
  • Si no estaba, lo añades y lo cuentas
  • Hasta que la cuenta sea 15

Este mecanismo es ineficiente por dos razones:

  1. Para mirar si el par (X,Y) ya había sido generado no queda más remedio que revisar todos los generados anteriormente, lo cual debe hacerse con otro bucle y comparando uno a uno. Esto es ineficiente, porque por cada iteración del bucle principal hay que hacer varias iteraciones en otro bucle interno.
  2. A medida que vas añadiendo pares (X,Y) al resultado, más probable es que te salgan repetidos, por lo que el número de "reintentos" para dar con uno que no estuviera ya va creciendo. Este problema sería muy grave si quisieras generar muchos pares, por ejemplo 98. Ya que el número de pares posibles es 100, dar con el último que no esté ya entre los 97 anteriores va a ser muy difícil y exigiría montones de reintentos.

Alternativa?

La alternativa que se me ocurre es un tanto complicada de implementar, pero fácil de entender. La idea es la siguiente:

  • Imagina que tienes una baraja de 100 cartas y que cada carta tiene escrito un par (X,Y) diferente
  • Mezclas esa baraja
  • Coges las 15 primeras cartas y eso te da 15 pares (X,Y) aleatorios entre los que no habrá repetidos.

Pero ¿cómo mezclar una baraja en C? Elaboremos un poco más el método, cambiando la mezcla de la baraja por otra alternativa que al final da el mismo resultado pero es más fácil de implementar.

  1. Creamos un array de 100 números (nuestra "baraja") y metemos en cada elemento un número de 0 al 99. Ese número será el par (X,Y). Si por ejemplo el número es 37, significará Y=3, X=7. La "baraja" empieza ordenada, es decir, el elemento k del array tiene valor k. La baraja comienza teniendo 100 cartas.
  2. Elegimos un número al azar entre 0 y la longitud de la baraja. Digamos que sale el número idx
  3. Sacamos la carta que está en el índice idx. Eso ya nos da un par (X,Y) y ha sido elegido al azar. Ahora hay que quitar esa carta de la baraja para evitar que salga de nuevo. Para ello
  4. Intercambiamos la carta que estaba en idx por la última carta de la baraja. Reducimos en 1 la longitud de la baraja
  5. Volvemos al paso 2 tantas veces como sea necesario.

Observa que cada vez que pasamos por 2 la baraja ha menguado. La primera vez elegimos un número entre 0 y 100. La segunda entre 0 y 99, luego entre 0 y 98, etc... El paso 4 es una forma de "compactar de nuevo" la baraja una vez eliminada la carta que estaba en posición idx. Se va desordenando la baraja, pero no importa ya que luego sacaremos otro elemento al azar de la misma, por lo que lo mismo da si estaba ordenada o no.

Ese método podría repetirse sin problema 98 veces (las cartas disponibles son menos cada vez, pero no hay que hacer "reintentos", sólo ir generando valores más pequeños de idx.

Implementación

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <time.h>
main(){
        int Filas , Columnas;
        int CantidadObjetos , CantidadTesoros , CantidadMinas ;

        Filas = 10;
        Columnas = 10;
        CantidadTesoros = 5 ;
        CantidadMinas = 10 ;
        CantidadObjetos = CantidadTesoros + CantidadMinas ; 

        int UbicacionObjetoX[CantidadObjetos] , UbicacionObjetoY[CantidadObjetos] ;
        int k ;

        // Variables para crear la "baraja virtual"
        int aux_len = Filas*Columnas;
        int aux[aux_len];

        // Inicialización de la "baraja"
        for (k=0;k<aux_len; k++) {
            aux[k] = k;
        }

        srand(time(NULL));
        for(k=0;k<CantidadObjetos;k++){
            int idx;
            int pos;
            // Elegir una carta al azar, entre las disponibles
            idx = rand()/(float)RAND_MAX*aux_len;
            // Esa carta nos dice que posicion (pos) ha salido
            pos = aux[idx];

            UbicacionObjetoX[k] = pos % Filas ;
            UbicacionObjetoY[k] = pos / Filas ;

            // Eliminar esa carta de la baraja
            aux[idx] = aux[aux_len-1];
            aux_len -= 1;
        }
    printf("Ubicaciones:\n");
    for (k=0;k<CantidadObjetos;k++) {
        printf("  X=%d, Y=%d\n", UbicacionObjetoX[k], UbicacionObjetoY[k]);
    }
}

Demo

Al ejecutar el programa sale esto:

Ubicaciones:
  X=5, Y=7
  X=1, Y=4
  X=9, Y=7
  X=7, Y=5
  X=8, Y=0
  X=4, Y=5
  X=6, Y=8
  X=1, Y=9
  X=0, Y=6
  X=2, Y=7
  X=5, Y=5
  X=8, Y=7
  X=4, Y=9
  X=7, Y=6
  X=9, Y=4

Ampliación

A petición del OP incluyo cómo se programaría la primera solución. En vez de un for queda más legible utilizar un while pues se ve más claramente que cuando se genera un valor repetido el contador no se incrementa (y ese contador es el índice en donde se van guardando los valores generados, por lo que no quedan huecos en el array).

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <time.h>
int main(){
        int Filas , Columnas;
        int CantidadObjetos , CantidadTesoros , CantidadMinas ;

        Filas = 10;
        Columnas = 10;
        CantidadTesoros = 5 ;
        CantidadMinas = 10 ;
        CantidadObjetos = CantidadTesoros + CantidadMinas ;

        int UbicacionObjetoX[CantidadObjetos] , UbicacionObjetoY[CantidadObjetos] ;
        int contador ;

        srand(time(NULL));
        contador = 0;  // Contador de objetos generados
        while (contador<CantidadObjetos) {
            int x, y;
            int repetido;  // Booleano que nos dirá si está repetido el par (X,Y)

            // Generar un par (X, Y)
            x = rand() % Filas;
            y = rand() % Columnas;
            // Mirar si ya estaba generado antes
            repetido = 0;    // Suponemos que no
            for (int i=0; i<contador; i++) {  // Y miramos entre los previamente generados
                if ((UbicacionObjetoX[i] == x) && (UbicacionObjetoY[i] == y)) {
                    // Si encontramos uno que ya estaba, cambiamos el booleano y hacemos break
                    // para dejar de mirar ya los siguientes
                    repetido = 1;
                    break;
                }
            }
            // Si no está repetido, lo añadimos
            if (repetido==0) {
                UbicacionObjetoX[contador] = x ;
                UbicacionObjetoY[contador] = y ;
                contador++;
            }
        }
    printf("Ubicaciones:\n");
    for (int i=0;i<CantidadObjetos;i++) {
        printf("  X=%d, Y=%d\n", UbicacionObjetoX[i], UbicacionObjetoY[i]);
    }
}

Para depuración puedes hacer que imprima un mensaje cuando encuentra un repetido. He comprobado que, aunque a veces genera los 15 del tirón, sin reintentos, muchas veces requiere uno o dos reintentos, y a veces hasta tres. No me he encontrado nunca un caso en que necesitase cuatro reintentos, por lo que al menos para este tamaño del problema esta solución no es tan mala. Si en vez de 15 hubiera que generar por ejemplo 50, el número de reintentos crecería mucho y sería preferible la primera solución.

2
  • Muchas gracias por tu respuesta. No voy a emplear números mayores y me ha sido muy útil tu consejo. Sin embargo, tengo curiosidad sobre el primer método que sugeriste. Si no es mucha molestia, podrías mostrarme el código de este? Según tengo entendido, al no contar un valor en el espacio del arreglo, este espacio queda vacío, pero cuando señalas porque el primer método es ineficiente, no mencionas esto. Asumo que entonces hay una forma de ubicar un valor en ese espacio mediante el primer método y que también solucione mi problema
    – juan foti
    Commented el 8 ago. 2022 a las 2:19
  • @juanfoti Respuesta editada para añadir la otra solución. Si esto resuelve tu consulta puedes marcar la respuesta como aceptada para cerrarla. Si te quedan dudas puedes seguir preguntando en comentarios.
    – abulafia
    Commented el 8 ago. 2022 a las 11:39

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.