using System;

public class Program

{

    public static void Main()

    {

        char[,] matrix = new char[6, 6] {

            { 'x', 'c','a','s','o','y' },

            { 'x', 'm','a','r','r','y' },

            { 'c', 'u','o','r','t','x' },

            { 'x', 'c','u','l','o','x' },

            { 'x', 'p','u','l','a','x' },

            { 'x', 'p','a','l','o','x' },

        };

​

        WordMatrix w = new WordMatrix(6);

        //string result = w.searchWord(matrix, 6, "culo");

        string result = w.searchWord(matrix, 6, "orto");

        if (!string.IsNullOrEmpty(result))

        {

            //stampa risultato

            Console.WriteLine(result);

            Console.WriteLine();

            //Stampa matrice di supporto per far vedere dove si trova il risultato

            w.print(6);

        }

        else

        {

            Console.Write("KO");

        }

​

        Console.ReadLine();

    }

    public class WordMatrix

    {

        public int[,] solution;

        int path = 1;

​

        //Praticamente costruisce una matrice uguale a quella di input inizializzata a 0, serve solo per rendere efficiente la ricerca.

        //Sostanzialmente il backtracking rende le cose più efficienti perchè tiene traccia delle celle visitate e dunque non ripete cose inutili

        //man mano che trova la parola la riempie con l'indice della parola trovata, ad esempio 0001234000 dove 1234 rappresenta la parola "culo"

        public WordMatrix(int N)

        {

            solution = new int[N, N];

            for (int i = 0; i < N; i++)

            {

                for (int j = 0; j < N; j++)

                {

                    solution[i,j] = 0;

                }

            }

        }

​

        //scorre x,y alla ricerca

        public string searchWord(char[,] matrix, int length, String word)

        {

            for (int i = 0; i < length; i++)

            {

                for (int j = 0; j < length; j++)

                {

                    if (search(matrix, word, i, j, 0, length))

                    {

                        return "Trovato a x:" + i + " y:" + j;

                    }

                }

            }

            return "";//non trovato se vuota

        }

​

        private bool search(char[,] matrix, String word, int row, int col, int index, int N)

        {

            //verifica che la cella corrente non sia già usata nella matrice di appoggio oppure che non sia diversa dal carattere ricercato, in tal caso false

            if (solution[row,col] != 0 || word[index] != matrix[row,col])

            {

                return false;

            }

​

            //index indica il numero di lettere trovate fin'ora, ovviamente quando è uguale alla lunghezza della parola cercata si ferma

            if (index == word.Length - 1)

            {

                // word is found, return true

                solution[row,col] = path++;

                return true;

            }

​

            // mark the current cell as 1

            solution[row,col] = path++;

​

            // check if cell is already used

            if (row + 1 < N && search(matrix, word, row + 1, col, index + 1, N))

            { // go

              // down

                return true;

            }

            if (row - 1 >= 0 && search(matrix, word, row - 1, col, index + 1, N))

            { // go

              // up

                return true;

            }

            if (col + 1 < N && search(matrix, word, row, col + 1, index + 1, N))

            { // go

              // right

                return true;

            }

            if (col - 1 >= 0 && search(matrix, word, row, col - 1, index + 1, N))

            { // go

              // left

                return true;

            }

​

            // if none of the option works out, BACKTRACK and return false

            solution[row,col] = 0;

            path--;

            return false;

        }

​

        public void print(int length)

        {

            for (int i = 0; i < length; i++)

            {

                for (int j = 0; j < length; j++)

                {

                    Console.Write(" " + solution[i, j]);

                }

                Console.WriteLine();

            }

        }

​

    }   

}