java - 垂直遍历二维数组以编程方式查找 "empty"集的有效方法是什么？

Question

首先，这不是作业 ;)。我正在尝试从头开始创建一个单词搜索游戏，但遇到了障碍，我需要一些指导。

我正在使用一个二维字符数组作为单词搜索的网格。我很乐意将单词水平放置在这些数组中，但我真的不知道如何垂直放置单词。

这就是我目前所拥有的，您应该能够复制/粘贴并运行它

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

打印出类似...

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

我需要在左侧/右侧随机填充它们，但我自己可以做到。

问题:像上面这样尝试将单词垂直放置到二维数组中的有效方法是什么？我最初的想法是向下计数所需的单词长度，如果找到 ? 以外的任何内容，则中断，并继续这样做，直到我找到该单词的空间。然而，一旦我考虑到单词重叠，这就变得不那么漂亮了。

有什么建议吗？

Answer 1

我在实现“Battleship”时用 C 做过类似的问题。不同的船只大小不同，您不能让它们相交。

一旦你有了垂直单词，你就需要检查你的水平单词是否也击中了它们。

我建议创建一个“Word”类，它是一个围绕 String 的精简类。您只需要跟踪以下内容。

1. 世界上的x,y位置/索引
2. 这个词是什么
3. 单词的长度(Java 中的 String 给你的)
4. 单词的方向(上下左右)

然后您创建一个方法来验证单词放置。 E.G，整个词必须在黑板上，并且没有冲突。您可以通过一系列线段对单词碰撞进行建模。这可以通过使用 rect to rect 碰撞算法来完成，其中一维几乎为 1。