Estoy escribiendo un acertijo de búsqueda de palabras en C# y me gustaría poder buscar la matriz bidimensional de caracteres de las palabras de una manera elegante.¿Cómo busco una matriz bidimensional en cualquier dirección?
Las búsquedas básicas de izquierda a derecha, de arriba a abajo, etc., no son difíciles de escribir, sin embargo, las cosas comienzan a ser un poco detalladas cuando se busca diagonalmente en la matriz. Lo tengo funcionando, pero estoy seguro de que hay una mejor solución por ahí.
Aquí hay un ejemplo de un rompecabezas que estoy tratando de resolver, cualquier idea sería muy apreciada.
BXXD
AXEX
TRXX
FXXX
BAT FRED
EDIT: Felicitaciones a Steve por darme la idea de buscar puntos de la brújula
EDIT: El resultado de la búsqueda necesita devolver las coordenadas x1, y1 y x2, y2 de las palabras dentro del ar rayo.
EDIT: Gracias a Antti por proporcionar un buen algoritmo para buscar la matriz.
Este es el resultado final que se me ocurrió. Lo he basado en el algoritmo de la respuesta de Antti, habiéndolo modificado para devolver las compensaciones de la matriz para el comienzo y el final de las palabras encontradas. Este algoritmo se usará en un juego de búsqueda de palabras que estoy escribiendo en WPF, para mis hijos. Gracias a todos por ayudarme. Publicaré un enlace aquí a la aplicación cuando sea respetable.
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);
}
}
Si mostrar su método actual que alguien podría tener un mejor método. Hasta que sepamos cómo lo está haciendo actualmente, realmente no podemos mejorarlo. – gingerbreadboy
Es largo y feo y no merece la pena criticarlo. Esperaba que alguien conociera mejor las estructuras de datos y los algoritmos que yo podría orientarme en la dirección correcta. –