logo标签列表

如何在任意方向上搜索二维数组

c#algorithm
8
我正在使用C#编写一个单词查找谜题，希望能够以一种优雅的方式搜索字符的二维数组中的单词。从左到右、从上到下等基本搜索不难实现，但当在这个数组中进行对角线搜索时，代码会变得有些冗长。我已经让它正常工作了，但我相信还有更好的解决方案。
以下是一个我正在尝试解决的谜题示例，非常感谢大家给出任何想法。
BXXD AXEX TRXX FXXX
要搜索的单词是BAT FRED。
编辑：感谢Steve提供了搜索罗盘点思路的建议。
编辑：搜索结果需要返回单词在数组中的x1、y1和x2、y2坐标。
编辑：感谢Antti提供了一个搜索数组的好算法。
这是我最终得出的结果。我基于Antti答案中的算法进行改进，使其返回任何找到的单词的开始和结束的数组偏移量。我正在使用这个算法编写一个Word Search游戏，用于我的孩子们的WPF。感谢大家的帮助，当这个应用达到可观状态时，我会在这里发布链接。
public class Range
{
    public Range(Coordinate start, Coordinate end)
    {
        Start = start;
        End = end;
    }

    public Coordinate Start { get; set; }
    public Coordinate End { get; set; }
}

public class Coordinate
{
    public Coordinate(int x, int y)
    {
        X = x;
        Y = y;
    }

    public int X { get; set; }
    public int Y { get; set; }
}

public class WordSearcher 
{
    public WordSearcher(char[,] puzzle)
    {
        Puzzle = puzzle;
    }

    public char[,] Puzzle { get; set; }

    // represents the array offsets for each
    // character surrounding the current one
    private Coordinate[] directions = 
    {
        new Coordinate(-1, 0), // West
        new Coordinate(-1,-1), // North West
        new Coordinate(0, -1), // North
        new Coordinate(1, -1), // North East
        new Coordinate(1, 0),  // East
        new Coordinate(1, 1),  // South East
        new Coordinate(0, 1),  // South
        new Coordinate(-1, 1)  // South West
    };

    public Range Search(string word)
    {
        // scan the puzzle line by line
        for (int y = 0; y < Puzzle.GetLength(0); y++)
        {
            for (int x = 0; x < Puzzle.GetLength(1); x++)
            {
                if (Puzzle[y, x] == word[0])
                {
                    // and when we find a character that matches 
                    // the start of the word, scan in each direction 
                    // around it looking for the rest of the word
                    var start = new Coordinate(x, y);
                    var end = SearchEachDirection(word, x, y);
                    if (end != null)
                    {
                        return new Range(start, end);
                    }
                }
            }
        }
        return null;
    }

    private Coordinate SearchEachDirection(string word, int x, int y)
    {
        char[] chars = word.ToCharArray();
        for (int direction = 0; direction < 8; direction++)
        {
            var reference = SearchDirection(chars, x, y, direction);
            if (reference != null)
            {
                return reference;
            }
        }
        return null;
    }

    private Coordinate SearchDirection(char[] chars, int x, int y, int direction)
    {
        // have we ve moved passed the boundary of the puzzle
        if (x < 0 || y < 0 || x >= Puzzle.GetLength(1) || y >= Puzzle.GetLength(0))
            return null;

        if (Puzzle[y, x] != chars[0])
            return null;

        // when we reach the last character in the word
        // the values of x,y represent location in the
        // puzzle where the word stops
        if (chars.Length == 1)
            return new Coordinate(x, y);

        // test the next character in the current direction
        char[] copy = new char[chars.Length - 1];
        Array.Copy(chars, 1, copy, 0, chars.Length - 1);
        return SearchDirection(copy, x + directions[direction].X, y + directions[direction].Y, direction);
    }
}
3
如果你展示你目前的方法，可能会有人有更好的方法。在我们了解你当前的做法之前，我们无法对其进行改进。 - gingerbreadboy
这段代码又长又难看，不值得浪费时间去批评。我希望有人比我更懂数据结构和算法，能够指引我正确的方向。 - Ian Oakes
5个回答
6

这个解决方案是用C++编写的，但原理相同。

如果您的谜题是由以下表示的：

char puzzle[N][N]

声明数组

int xd[8] = { -1, -1,  0, +1, +1, +1,  0, -1 };
int yd[8] = {  0, -1, -1, -1,  0, +1, +1, +1 };

当你想要检查单词 'w' 是否可以在位置 (x, y) 的方向 d（d 介于0和7之间）中找到时，只需执行以下操作

bool wordsearch(const char *w, int x, int y, int d) {
  if (*w == 0) return true; // end of word
  if (x<0||y<0||x>=N||y>=N) return false; // out of bounds
  if (puzzle[y][x] != w[0]) return false; // wrong character
  // otherwise scan forwards
  return wordsearch(w + 1, x + xd[d], y + yd[d], d); 
}

然后是驱动程序

bool wordsearch(const char *w, int x, int y) {
  int d;
  for (d=0;d<8;d++)
    if (wordsearch(w, x, y, d)) return true;
  return false;
}

bool wordsearch(const char *w) {
  int x, y;
  for (x=0;x<N;x++) for(y=0;y<N;y++) if (wordsearch(w, x, y)) return true;
  return false;
}
我会尝试这个并让你知道，我有一个不太优雅的解决方案（见编辑）正在运行，但我也会尝试这个。 - Ian Oakes
非常聪明，实际上相当出色。花了一些时间才理解，但我应该能够将其转换为C#并返回xy的值。这正是我正在寻找的类型算法，简短而简洁。感谢您的帮助。这是我为孩子们编写的WPF游戏所需的。 - Ian Oakes
4
这是应该使用trie数据结构解决的典型问题：http://en.wikipedia.org/wiki/Trie 一旦您有了包含所有目标单词的字典，您可以遍历二维数组中的每个位置，并调用一个递归函数来扩展所有8个方向。大致如下：
void Explore(TwoDimArray puzzle, Point2D currentCell, string currentMatch, List<string> foundSolutions);

如果出现以下情况，递归将停止：
- 找到了匹配项。
- currentMatch + currentCell的字符不再构成可能的匹配项。
- currentCell位置不再在谜题区域内。

+1 for trie，尽管我认为递归并没有太多意义。对于任何为人类设计的纵横填字游戏，即使是暴力破解也可以工作。尽管Trie可能比OP需求更强大一些。 - Brian
2
public class Range
{
    public Range(Coordinate start, Coordinate end)
    {
        Start = start;
        End = end;
    }

    public Coordinate Start { get; set; }
    public Coordinate End { get; set; }
}

public class Coordinate
{
    public Coordinate(int x, int y)
    {
        X = x;
        Y = y;
    }

    public int X { get; set; }
    public int Y { get; set; }
}

public class WordSearcher 
{
    public WordSearcher(char[,] puzzle)
    {
        Puzzle = puzzle;
    }

    public char[,] Puzzle { get; set; }

    // represents the array offsets for each
    // character surrounding the current one
    private Coordinate[] directions = 
    {
        new Coordinate(-1, 0), // West
        new Coordinate(-1,-1), // North West
        new Coordinate(0, -1), // North
        new Coordinate(1, -1), // North East
        new Coordinate(1, 0),  // East
        new Coordinate(1, 1),  // South East
        new Coordinate(0, 1),  // South
        new Coordinate(-1, 1)  // South West
    };

    public Range Search(string word)
    {
        // scan the puzzle line by line
        for (int y = 0; y < Puzzle.GetLength(0); y++)
        {
            for (int x = 0; x < Puzzle.GetLength(1); x++)
            {
                if (Puzzle[y, x] == word[0])
                {
                    // and when we find a character that matches 
                    // the start of the word, scan in each direction 
                    // around it looking for the rest of the word
                    var start = new Coordinate(x, y);
                    var end = SearchEachDirection(word, x, y);
                    if (end != null)
                    {
                        return new Range(start, end);
                    }
                }
            }
        }
        return null;
    }

    private Coordinate SearchEachDirection(string word, int x, int y)
    {
        char[] chars = word.ToCharArray();
        for (int direction = 0; direction < 8; direction++)
        {
            var reference = SearchDirection(chars, x, y, direction);
            if (reference != null)
            {
                return reference;
            }
        }
        return null;
    }

    private Coordinate SearchDirection(char[] chars, int x, int y, int direction)
    {
        // have we ve moved passed the boundary of the puzzle
        if (x < 0 || y < 0 || x >= Puzzle.GetLength(1) || y >= Puzzle.GetLength(0))
            return null;

        if (Puzzle[y, x] != chars[0])
            return null;

        // when we reach the last character in the word
        // the values of x,y represent location in the
        // puzzle where the word stops
        if (chars.Length == 1)
            return new Coordinate(x, y);

        // test the next character in the current direction
        char[] copy = new char[chars.Length - 1];
        Array.Copy(chars, 1, copy, 0, chars.Length - 1);
        return SearchDirection(copy, x + directions[direction].X, y + directions[direction].Y, direction);
    }
}
2
在列表或其他数据结构中保留您正在查找的每个单词的首字母。按顺序搜索每个字母。如果它是您要搜索的单词的第一个字母，那么在其周围搜索第二个字母。如果在单词中找到第二个字母，则在具有方向枚举的单词对象中注明方向，例如 {N = 0，NE，E，SE，S，SW，W，NW}。然后只需按照该方向进行搜索，直到确定未找到单词或已找到为止。关键是让搜索对象知道它正在查看多少个单词。因此，如果您正在寻找cater和cattle，如果找到C-A-T向东北走，它可能是任何一个。此外，如果找到F，则需要确保检查每个方向，因为您可以将FRIAR向东和FAT向西。然后，简单地确保不越界，因为NE是X + 1 Y-1等。
我最初也认为递归是首选，但问题在于如果你编写一个递归函数来搜索所有8个方向，你可能会发现单词在每个方向上都蜿蜒曲折，并且在最坏的情况下再次使用字母来构成像“racecar”这样的单词。这就是为什么我建议找到字母并选择一个方向进行跟随-以防止这种情况发生。如果您使用递归并发送一个标志以检查所有方向，那么您基本上已经打败了使用递归的目的。 - Steve H.
1
不要使用二维数组来解决这个谜题。对于一个NxM的单词搜索，使用一个大小为(N+2)*(M+2)的数组。在你的谜题的四周加上1个字符的边界。所以例子变成了： 
......
.BXXD.
.AXEX.
.TRXX.
.FXXX.
......
其中点号是填充字符, 所有这些实际上都是一维数组。
称新网格的宽度为行跨度(S), 您现在可以创建一个8个方向“向量”D=[ -S-1, -S, -S+1, -1, 1, S-1, S, S+1 ]的数组。使用此数组，您可以通过使用Puzzle [position + D [direction]]从任何位置在网格中查看其任意方向的邻居来解决问题。
当然，您的位置现在是单个变量而不是一对坐标。边界周围的填充告诉您是否已到达棋盘的边缘，并且应该是内部谜题中从未使用过的字符。
使用填充字符+1。通过避免边界测试，您可以在搜索例程中获得惊人的复杂性降低。 - Loren Pechtel
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接