Come si cerca una matrice bidimensionale in qualsiasi direzione

Question

Sto scrivendo un puzzle di ricerca di parole in C# e mi piacerebbe essere in grado di cercare la matrice bidimensionale di caratteri per le parole in modo elegante.

Le ricerche di base da sinistra a destra, dall'alto in basso ecc. Non sono difficili da scrivere, tuttavia le cose iniziano a diventare un po 'prolisse durante la ricerca in diagonale sull'array. Ho funzionato, ma sono sicuro che c'è una soluzione migliore là fuori.

Ecco un esempio di un puzzle che sto cercando di risolvere, qualsiasi idea sarebbe molto apprezzata.

BXXD
AXEX
TRXX
FXXX

BAT FRED

EDIT: Complimenti a Steve per avermi dato l'idea di cercare punti cardinali

EDIT: Il risultato della ricerca deve restituire le coordinate x1, y1 e x2, y2 delle parole all'interno dell'ar ray.

MODIFICA: Grazie ad Antti per aver fornito un buon algoritmo per la ricerca dell'array.

Questo il risultato finale che ho trovato. L'ho basato sull'algoritmo nella risposta di Antti, dopo averlo modificato per restituire gli offset dell'array per l'inizio e la fine di qualsiasi parola trovata. Questo algoritmo verrà utilizzato per il gioco di ricerca di parole che sto scrivendo in WPF, per i miei figli. Grazie a tutti per avermi aiutato. Inserirò un link qui per l'app quando è rispettabile.

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

questa soluzione è scritto in C++ ma il principio è LA STESSA

Se il puzzle è rappresentato da

char puzzle[N][N] 

dichiarano gli array

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

e poi quando si desidera controllare se la parola "w" può essere trovata nella posizione (x, y) in direzione d (d tra 0 e 7 inclusi), basta fare

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

e poi i piloti

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

Answer 2

Mantieni le prime lettere di ogni parola che cerchi in una lista o in una tale struttura dati. Cerca ogni lettera in ordine. Se è la prima lettera di una parola che stai cercando, cerca in ogni lettera intorno ad essa una seconda lettera. Se trovi una seconda lettera in una parola, nota la direzione in un oggetto parola che ha un enum di direzione, cioè {N = 0, NE, E, SE, S, SW, W, NW}. Quindi segui semplicemente quella direzione finché non hai determinato che la parola non viene trovata o trovata. La chiave è che l'oggetto di ricerca sappia quante parole sta guardando. Quindi, se stai cercando sia cibo che bestiame, se trovi il C-A-T in direzione nordest, potrebbe esserlo. Inoltre, se trovi una F dovrai assicurarti di controllare tutte le direzioni perché puoi avere FRIAR andando ad est e FAT andando ad ovest. Allora è semplice come fare in modo di non andare fuori dai limiti, perché NE è X + 1 Y-1, ecc ...

Answer 3

Questo è il problema tipico in cui si consiglia di utilizzare la struttura dati trie: http://en.wikipedia.org/wiki/Trie

Una volta che hai un dizionario con tutte le parole target, passi attraverso ogni posizione del tuo array a due dimensioni e chiama una funzione ricorsiva che espande tutti gli 8 modi. Qualcosa sulla falsariga di.

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

Ti fermi ricorsività se:
- si trova una corrispondenza.
- Il carattere currentMatch + currentCell non costituisce più una possibile corrispondenza.
- La posizione currentCell non è più all'interno dell'area del puzzle.

Answer 4

NON utilizzare un array bidimensionale per il puzzle. Per una ricerca di parole NxM, utilizzare un array di (N + 2) * (M + 2). Metti il ​​padding di 1 personaggio intorno al tuo puzzle. Quindi l'esempio diventa:

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

Dove i periodi sono il riempimento e tutto ciò è in realtà un array 1d.

Chiamando la larghezza della nuova griglia l'intervallo di riga (S), è ora possibile creare un array di 8 "vettori" di direzione D = [-S-1, -S, -S + 1, -1, 1 , S-1, S, S + 1]. Usando questo, puoi guardare da qualsiasi posizione nella griglia Puzzle [posizione] al suo vicino in qualsiasi direzione usando Puzzle [posizione + D [direzione]].

La tua posizione ovviamente è ora una singola variabile invece di una coppia di coordinate. L'imbottitura attorno al bordo ti dice se hai raggiunto il bordo della tavola e dovrebbe essere un personaggio che non viene mai usato all'interno del puzzle.

Answer 5

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