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

Question

我正在用C#编写一个单词搜索拼图,我希望能够以优雅的方式搜索二维字符数组.

从左到右,从上到下等基本搜索并不难写,但是当在对角线上搜索时,事情开始变得有点冗长.我已经开始工作,但我确信那里有更好的解决方案.

这是我想要解决的一个难题的例子,任何想法将不胜感激.

BXXD
AXEX
TRXX
FXXX

BAT FRED

编辑:感谢史蒂夫给我一个搜索罗盘点的想法

编辑:搜索结果需要返回数组中单词的x1,y1和x2,y2坐标.

编辑:感谢Antti为搜索数组提供了一个很好的算法.

这是我想出的最终结果.我基于Antti的答案中的算法,修改它以返回任何单词的开头和结尾的数组偏移量.这个算法将用于我在WPF中为我的孩子写的Word Search游戏.感谢大家帮助我.当它受到尊重时,我会在这里发布一个链接到应用程序.

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

Answer 1

这个解决方案是用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 };

然后当你想检查在方向d(d和0之间的d)的位置(x,y)是否可以找到单词'w'时,只需要做

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