¿Cuál es un método efectivo para atravesar una 2d matriz verticalmente para encontrar programáticamente un conjunto "vacío"?

Question

En primer lugar, esto no es tarea;). Intento crear un juego de sopa de letras desde cero y he topado con una barrera en la que necesito orientación.

Estoy usando una matriz 2d de caracteres para la cuadrícula de una sopa de letras. Me siento cómodo colocando palabras en estos arreglos horizontalmente, pero estoy realmente atrapado por ideas sobre cómo hacerlo verticalmente.

Esto es lo que tengo hasta ahora, sólo debe ser capaz de copiar/pegar y ejecutarlo

import java.util.ArrayList; 
import java.util.List; 

public class WordGame 
{ 
    private static List<String> words = new ArrayList<String>(); 
    private static int longestWordLength = 0; 
    private static int padSize = 4; 
    private static char[][] grid = null; 

    public static void main(String[] args) 
    { 
     initialiseWords(); 
     workOutLongestWord(); 
     setupGrid(); 
     printIt(); 
    } 

    private static void printIt() 
    { 
     for (int i = 0; i < grid.length; i++) 
     { 
      for (int j = 0; j < grid.length; j++) 
      { 
       System.out.print(grid[i][j]); 
      } 
      System.out.print("\n"); 
     } 
    } 

    private static void setupGrid() 
    { 
     grid = new char[longestWordLength + padSize][longestWordLength + padSize]; 

     for (int i = 0; i < grid.length; i++) 
     { 
      String w = (i >= words.size()) ? "?" : words.get(i); 
      for (int j = 0; j < grid.length; j++) 
      { 
       grid[i][j] = (j >= w.length()) ? '?' : w.charAt(j); 
      } 
     } 
    } 

    private static void workOutLongestWord() 
    { 
     for (String word : words) 
     { 
      if (word.length() > longestWordLength) 
      { 
       longestWordLength = word.length(); 
      } 
     } 
    } 

    private static void initialiseWords() 
    { 
     words.add("monkey"); 
     words.add("cow"); 
     words.add("elephant"); 
     words.add("kangaroo"); 
    } 
} 

que imprime algo como ...

monkey?????? 
cow????????? 
elephant???? 
kangaroo???? 
???????????? 
???????????? 
???????????? 
???????????? 
???????????? 
???????????? 
???????????? 
???????????? 

necesito los rellenan aleatoriamente en el lado izquierdo/derecho, pero puedo hacerlo yo mismo.

Pregunta: ¿Cuál es una forma efectiva de intentar colocar palabras verticalmente en una matriz 2D como la anterior? Mi idea inicial fue contar hacia abajo la longitud de palabra requerida, rompiendo si se encuentra algo más que ?, y seguir haciendo esto hasta que pueda encontrar un espacio para la palabra. Sin embargo, esto no se vuelve bonito una vez que tomo en cuenta la superposición de palabras.

¿Alguna sugerencia?

Answer 1

Hice un problema similar en C al implementar "Battleship". Diferentes naves eran de diferentes tamaños y no se podía hacer que se cruzaran.

Una vez que tenga palabras verticales, deberá comprobar si sus palabras horizontales también las afectan.

Sugiero hacer una clase "Word" que es una clase delgada alrededor de String. Solo necesita realizar un seguimiento de lo siguiente.

1. x, y posición/índice en el mundo
2. lo que la palabra es
3. la longitud de la palabra (que le ha asignado cadena en Java)
4. La orientación de la palabra (hasta abajo izquierda derecha)

Luego, crea un método que valida la colocación de palabras. E.G, toda la palabra tiene que estar en el tablero, y no hay una colisión. Puede modelar la colisión de palabras mediante una serie de segmentos de línea. Esto podría hacerse mediante el uso de algoritmos de colisión rect a rect, donde una dimensión es casi 1.

Answer 2

Verticalmente debería poder utilizar el mismo método que horizontalmente. Tal como dijiste, comienza en un punto y muévete hacia abajo mientras tengas espacios vacíos o el espacio contenga la letra de la palabra que deseas insertar.