Co to jest skuteczna metoda przechodzenia w pionie 2d w celu programowego znalezienia "pustego" zestawu?

Question

Po pierwsze, to nie jest praca domowa;). Próbuję stworzyć od zera wyszukiwarkę słów i uderzyłem w barierę, potrzebuję wskazówek.

Używam tablicy 2d znaków dla siatki wyszukiwania słów. Czuję się dobrze z umieszczaniem słów w tych tablicach poziomo, ale naprawdę utknąłem na pomysły, jak to zrobić w pionie.

To, co do tej pory, należy po prostu być w stanie skopiować/wkleić go i uruchomić go

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"); 
    } 
} 

Który wypisuje coś takiego ...

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

muszę losowo wyłóż je po lewej/prawej stronie, ale mogę to zrobić sam.

Pytanie: Jaki jest skuteczny sposób próbowania umieszczania wyrazów pionowo w tablicy 2d, jak wyżej? Moja początkowa myśl polegała na policzeniu w dół dla wymaganej długości słowa, zerwaniu, jeśli znajdzie się coś innego niż ? i kontynuowanie tego, dopóki nie znajdę miejsca na słowo. Jednak nie jest to zbyt piękne, gdy uwzględniam nakładanie się słów.

Jakieś wskazówki?

Answer 1

Zrobiłem podobny problem w C przy realizacji "Battleship". Różne statki miały różne rozmiary i nie można było ich przecinać.

Gdy masz już pionowe słowa, musisz sprawdzić, czy twoje poziomy słowa również je uderzają.

Proponuję utworzyć klasę "Word", która jest cienką klasą wokół String. Musisz tylko śledzić następujące rzeczy.

1. x, y Pozycja/wskaźnik na świecie
2. Jakie słowo jest
3. długość słowa (podany przez String w Javie)
4. orientacji słowa (w górę w dół lewy prawy)

Następnie tworzy się metodę potwierdzającą umieszczenie słowa. E.G, Całe słowo musi znajdować się na planszy i nie ma kolizji. Można modelować kolizję słów przez szereg segmentów linii. Można to zrobić za pomocą algorytmów kolizji prostopadle do prostych, gdzie jeden wymiar jest prawie 1.

Answer 2

W pionie powinna istnieć możliwość użycia tej samej metody, co poziomo. Tak jak powiedziałeś, zacznij w jednym miejscu i ruszaj tak długo, jak masz puste miejsca lub spacja zawiera literę od słowa, które chcesz wstawić.