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

这个解决方案是用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”是否位于方向d(d介于0和7之间,包括0和7之间)的位置(x,y)时,只需执行以下操作即可

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

这是您应该使用trie数据结构的典型问题: http://en.wikipedia.org/wiki/Trie

void Explore(TwoDimArray puzzle, Point2D currentCell, string currentMatch, List<string> foundSolutions);

如果出现以下情况,则停止递归:
-你找到匹配的。
-currentMatch+currentCell的字符不再构成可能的匹配。
-当前单元格位置不再位于拼图区域内。

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

不要在拼图中使用二维数组。对于NxM单词搜索,使用(N+2)*(M+2)的数组。将1个字符的填充放在拼图的四周。因此,这个例子变成:

......
.BXXD.
.AXEX.
.TRXX.
.FXXX.
......

其中句点是填充,所有这些实际上都是1d数组。

将新网格的宽度称为行跨度,现在可以创建8个方向“向量”D=[-S-1,-S,-S+1,-1,1,S-1,S,S+1]的数组。使用此功能,您可以使用拼图[position+D[direction]]从网格拼图[position]中的任何位置向任何方向查看其相邻位置。

当然,你的位置现在是一个变量,而不是一对坐标。边框周围的填充告诉您是否已到达棋盘边缘,并且应该是一个从未在拼图内部使用过的字符。