מריה בוטוסוב

נותנים מערך דו-מימדי של תווים (לוח) ורשימה של מילים שצריך למצוא בלוח. יש לכתוב אלגוריטם שמוצא את כל המילים.

//O(nm*8^s + ws) time | O(nm + ws) space
public static List<string> BoggleBoard(char[,] board, string[] words) {
    List<string> res = new List<string>();
    TrieNode root = new TrieNode('#');
    BuildTrieTree(root, words);
    for(int i = 0; i < board.GetLength(0); i++) {
        for(int j = 0;  j < board.GetLength(1); j++) {
            if(root.Children[board[i, j]] != null)
                DFS(board, root, i, j, res);
        }
    }		
    return res;
}
	
private static void DFS(char[,] board, TrieNode curr, int i, int j, List<string> res) {
    int[,] directions = new int[,] {{-1, 0}, {1, 0}, {0, 1}, {0, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
    if(i < 0 || i >= board.GetLength(0) || j < 0 || j >= board.GetLength(1))
        return;
    char c = board[i, j];
    if(c == '#' || curr.Children[c] == null)
        return;
		
    curr = curr.Children[c];
    if(curr.word != "") {
        res.Add(curr.word);
        curr.word = "";
    }
    board[i, j] = '#';
		
    for(int d = 0; d < directions.GetLength(0); d++)
        DFS(board, curr, i + directions[d,0], j + directions[d,1], res);
		
    board[i, j] = c;
}
	
private static void BuildTrieTree(TrieNode root, string[] words) {
    foreach(string word in words) {
        TrieNode curr = root;
        foreach(char c in word) {
            if(curr.Children[c] == null)
                curr.Children[c] = new TrieNode(c);
            curr = curr.Children[c];
        }
        curr.word = word;
    }
}
 
public class TrieNode {
    public char c;
    public string word;
    public TrieNode[] Children;
    public TrieNode(char c) {
        this.c = c;
        this.word = "";
        Children = new TrieNode[128];
    }
}