using System;

using System.Collections.Generic;

​

public class Program

{

    public abstract class PuzzleSolver {

        protected struct SearchContext {

            public SearchContext((int x, int y) puzzlePos, string word,

                                 int wordPos, Stack<(int, int)> path) {

                PuzzlePos = puzzlePos;

                Word = word;

                WordPos = wordPos;

                Path = path;

            }

​

            public (int x, int y) PuzzlePos { get; }

            public string Word { get; }

            public int WordPos { get; }

            public Stack<(int, int)> Path { get; }

​

            public bool IsCompleted() {

                return WordPos >= Word.Length - 1;

            }

        }

​

        protected static readonly (int x, int y)[] Siblings = new (int x, int y)[] {

            (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1) };

​

        protected readonly char[,] _puzzle;

        protected readonly int _width, _height;

​

        public PuzzleSolver(char[,] puzzle) {

            if (puzzle == null) {

                throw new ArgumentNullException(nameof(puzzle));

            }

​

            _puzzle = Initiate(puzzle);

​

            _width = _puzzle.GetLength(0);

            _height = _puzzle.GetLength(1);

        }

​

        protected virtual char[,] Initiate(char[,] puzzle) {

            var w = puzzle.GetLength(0);

            var h = puzzle.GetLength(1);

​

            var result = new char[w, h];

​

            if (w > 0 && h > 0) {

                for (var x = 0; x < w; x++) {

                    for (var y = 0; y < h; y++) {

                        result[x, y] = char.ToLowerInvariant(puzzle[x, y]);

                    }

                }

            }

​

            return result;

        }

​

        protected virtual bool IsValid(string word) {

            if (!(word?.Length > 0)) {

                return false;

            }

​

            foreach (var ch in word) {

                if (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))) {

                    return false;

                }

            }

            return true;

        }

​

        public bool Exists(string word) {

            if (_width > 0 && _height > 0) {

                word = word?.ToLowerInvariant();

                return IsValid(word) && CheckExists(word);

            }

            return false;

        }

​

        protected virtual bool CheckExists(string word) {

            return false;

        }

    }

​

    public class BruteForceSolver : PuzzleSolver {

        public BruteForceSolver(char[,] puzzle)

            : base(puzzle) { }

​

        protected override bool CheckExists(string word) {

            var firstChar = word[0];

​

            for (var x = 0; x < _width; x++) {

                for (var y = 0; y < _height; y++) {

                    if (_puzzle[x, y] == firstChar &&

                        Exists(new SearchContext((x, y), word, 1, new Stack<(int, int)>()))) {

                        return true;

                    }

                }

            }

            return false;

        }

​

        private bool Exists(SearchContext context) {

            context.Path.Push(context.PuzzlePos);

​

            var result = false;

            var ch = context.Word[context.WordPos];

​

            foreach (var sibling in Siblings) {

                (int x, int y) p = (context.PuzzlePos.x + sibling.x,

                                    context.PuzzlePos.y + sibling.y);

​

                if (p.x < 0 || p.x == _width ||

                    p.y < 0 || p.y == _height) {

                    continue;

                }

​

                if (_puzzle[p.x, p.y] == ch && !context.Path.Contains(p)) {

                    result = context.IsCompleted() ?

                                true :

                                Exists(new SearchContext(p, context.Word, context.WordPos + 1, context.Path));

​

                    if (result) {

                        break;

                    }

                }

            }

​

            if (!result) {

                context.Path.Pop();

            }

​

            return result;

        }

    }

​

    // Slover for the first time, much memory usage than BruteForceSolver, better for repeatedly usage

    public class RepeatableSolver : PuzzleSolver {

        private HashSet<(int, int)>[] _charIndex = new HashSet<(int, int)>[(int)'z' - (int)'a'];

​

        public RepeatableSolver(char[,] puzzle)

            : base(puzzle) { }

​

        protected override char[,] Initiate(char[,] puzzle) {

            var w = puzzle.GetLength(0);

            var h = puzzle.GetLength(1);

​

            var result = new char[w, h];

​

            if (w > 0 && h > 0) {

                for (var x = 0; x < w; x++) {

                    for (var y = 0; y < h; y++) {

                        var ch = char.ToLowerInvariant(puzzle[x, y]);

                        result[x, y] = ch;

​

                        if (ch >= 'a' && ch <= 'z') {

                            var charIndex = ch - 'a';

                            var possitions = (_charIndex[charIndex] != null) ?

                                                _charIndex[charIndex] :

                                                (_charIndex[charIndex] = new HashSet<(int, int)>());

​

                            possitions.Add((x, y));

                        }

                    }

                }

            }

​

            return result;

        }

​

        protected override bool CheckExists(string word) {

            var firstChar = word[0];

            var index = _charIndex[firstChar - 'a'];

​

            if (index != null) {

                foreach (var pos in index) {

                    if (Exists(new SearchContext(pos, word, 1, new Stack<(int, int)>()))) {

                        return true;

                    }

                }

            }

            return false;

        }

​

        private bool Exists(SearchContext context) {

            var ch = context.Word[context.WordPos];

            var index = _charIndex[(int)ch - 'a'];

​

            if (index == null) {

                return false;

            }

​

            context.Path.Push(context.PuzzlePos);

            var result = false;

​

            foreach (var sibling in Siblings) {

                (int x, int y) p = (context.PuzzlePos.x + sibling.x,

                                    context.PuzzlePos.y + sibling.y);

​

                if (index.Contains(p) && !context.Path.Contains(p)) {

                    result = context.IsCompleted() ?

                                true :

                                Exists(new SearchContext(p, context.Word, context.WordPos + 1, context.Path));

​

                    if (result) {

                        break;

                    }

                }

            }

​

            if (!result) {

                context.Path.Pop();

            }

​

            return result;

        }

    }

​

    public static void Main()

    {

        var puzzle = new char[,] {

            { '.', '.', '.', '.', '.', '.', '.', 'n', '.', '.' },

            { '.', '.', '.', '.', '.', '.', 'a', '.', '.', '.' },

            { '.', 'n', '.', '.', '.', 'g', '.', '.', '.', '.' },

            { '.', '.', 'a', '.', 'o', '.', '.', '.', '.', '.' },

            { '.', 'a', 'a', 'd', 'a', '.', '.', '.', '.', '.' },

            { '.', '.', 'k', 'i', '.', '.', '.', '.', '.', '.' },

            { '.', '.', '.', '.', 'f', '.', '.', '.', '.', '.' }

        };

​

        var testSet = new [] { "dogan", "nagod", "akif", "fika", "kaan", "naak", "kaaan", "kaaaan", "kağan", "kagan" };

​

        PuzzleSolver solver = new BruteForceSolver(puzzle);

​

        foreach (var word in testSet) {

            var result = solver.Exists(word) ? "exists" : "not exists";

            Console.WriteLine($"Brute force solver, {word} {result}");

        }

​

        solver = new RepeatableSolver(puzzle);

​

        foreach (var word in testSet) {

            var result = solver.Exists(word) ? "exists" : "not exists";

            Console.WriteLine($"Repeatable solver, {word} {result}");

        }   }

}