using System;

using System.Collections.Generic;

public class Program

{

    public class TrieNode {

        public Dictionary<char, TrieNode> Children;

        public String word;

        public TrieNode() {

            Children = new Dictionary<char, TrieNode>();

            word = null;

        }

    }

    public class Trie {

        public TrieNode root;

​

        /** Initialize your data structure here. */

        public Trie() {

            root = new TrieNode();

        }

        public Trie(List<string> words) {

            root = new TrieNode();

            foreach(string word in words) {

                Insert(word);

            }

        }

        /** Inserts a word into the trie. */

        public void Insert(string word) {

            TrieNode cur = root;

​

            for(int i = 0; i < word.Length; i++) {

                if (!cur.Children.ContainsKey(word[i])) {

                    TrieNode next = new TrieNode();

                    cur.Children.Add(word[i], next);

                    cur = next;

                } else {

                    cur = cur.Children[word[i]];

                }

​

​

            }

            cur.word = word; 

​

        }

    }

    public class BoggleGame {

        private char[][] board;

        private Trie trie;

        private int m;

        private int n;

        public List<string> maxWordList;

        public BoggleGame(char[][] b, List<string> words) {

            board = b;

            m = board.Length;

            n = board[0].Length;

            trie = new Trie(words);

            maxWordList = new List<string>();

        }

        public void findWords() {

            for(int i = 0; i < m; i++) {

                for(int j = 0; j < n; j++) {

                    backtrack(new List<string>(), i, j, trie.root);

                }

            }

        }

        private void backtrack(List<string> wordList, int i, int j, TrieNode node) {

            if (!inBound(i, j))

                return;

            if (board[i][j] == '#') // visited

                return;

            if (!node.Children.ContainsKey(board[i][j]))

                return;

            char ch = board[i][j];

            TrieNode nextNode = node.Children[ch];

            board[i][j] = '#';

            if (nextNode.word != null) {

                wordList.Add(nextNode.word);

                if (wordList.Count > maxWordList.Count) {

                    maxWordList = new List<string>(wordList);

                }

                for(int r = 0; r < m; r++ ) {

                    for(int c = 0; c < n; c++) {

                        backtrack(wordList, r, c, trie.root);

                    }

                }

                wordList.RemoveAt(wordList.Count -1);

            } else {

                for(int x = -1; x <= 1; x++) {

                    for(int y = -1; y <= 1; y++) {

                        backtrack(wordList, i + x, j + y, nextNode);

                    }

                }

            }

            board[i][j] = ch;

            return;

        }

        private bool inBound(int i, int j) {

            return i >= 0 && i < m && j >= 0 && j < n;

        }

    }

    public static void Main()

    {

        char[][] board = new char[][]{

                new char[]{'o','a','a','n'},

                new char[]{'e','t','a','e'},

                new char[]{'i','h','k','r'},

                new char[]{'i','f','l','v'}};

        List<string> words = new List<string>() {"oath","ak","klf", "ii", "rena"};

        BoggleGame game = new BoggleGame(board, words);

        game.findWords();

        game.maxWordList.ForEach(w => Console.Write("{0} ", w));

    }

}