Я пишу головоломку для поиска слов в C #, и я хотел бы иметь возможность элегантно искать слова в двумерном массиве символов.
Простой поиск слева направо, сверху вниз и т. Д. Написать несложно, однако при поиске по диагонали в массиве все становится немного многословным. У меня это работает, но я уверен, что есть лучшее решение.
Вот пример головоломки, которую я пытаюсь решить, любые идеи будут высоко оценены.
BXXD
AXEX
TRXX
FXXX
Летучая мышь Фред
РЕДАКТИРОВАТЬ: Престижность Стиву за предоставленную мне идею поиска точек компаса
РЕДАКТИРОВАТЬ: В результате поиска необходимо вернуть координаты x1, y1 и x2, y2 слов в массиве.
РЕДАКТИРОВАТЬ: Спасибо Antti за предоставленный хороший алгоритм для поиска в массиве.
Это окончательный результат, который я придумал. Я основал его на алгоритме в ответе Антти, изменив его так, чтобы он возвращал смещения массива для начала и конца всех найденных слов. Этот алгоритм будет использоваться для моих детей в игре «Поиск слова», которую я пишу в 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);
}
}