Найти количество различных маршрутов, ведущих к спасению узника из замка

using System.Collections.Generic;
using System.Linq;
using System.Collections;
 
namespace GraphSolution
{
    public class Graph
    {
        public int[,] Schema;                                                   // adjacency Matrix
        public ArrayList AttainableNodes = new ArrayList();
        public List<Dependency> Dependencies { get; private set; }
        public int[,] NumerableSchema;
        /// <summary>
        /// Returns graph
        /// </summary>
        /// <returns></returns>
        public Graph(int[,] schema)
        {
                this.Schema = schema;
                this.NumerableSchema = new int[schema.GetLength(0),schema.GetLength(1)];
                int N = this.Schema.GetLength(0);
                int M = this.Schema.GetLength(1);
            # region Смотрим есть ли соседние открытые комнаты и открываем в них двери(Создаем ребра + топографически сортируем)
            //        
            //         [i+1,j]
            //            ^
            //            |
            //[i,j-1]-->[i,j]--->[i,j+1]
            //            ^
            //            |
            //         [i-1,j]
 
            this.Dependencies = new List<Dependency>();                                                                 //Empty list of dependencies
            for (int i = 0; i < N; i++)
                for (int j = 0; j < M; j++)
                {
                    # region если текущая комната открыта то создаем от нее связи "вверх по нумерации"
                    if (this.Schema[i, j] == 1)                                                                         //current node is available
                    {
                        if ((i + 1) < N && this.Schema[i + 1, j] == 1)                                                  //next node exist and available
                        {
                            Dependency dependency1 = new Dependency(i * M + j, (i + 1) * M + j);
                            if (Dependencies.Find(_dependency => (_dependency.NodeFrom == dependency1.NodeFrom &&
                                                                _dependency.NodeTo == dependency1.NodeTo)) == null)
                                Dependencies.Add(dependency1);
                        }
                        if ((j + 1) < M && this.Schema[i, j + 1] == 1)                                                  //next node exist and available
                        {
                            Dependency dependency2 = new Dependency(i * M + j, i * M + j + 1);
                            if (Dependencies.Find(_dependency => ((_dependency.NodeFrom == dependency2.NodeFrom) &&
                                                                  (_dependency.NodeTo == dependency2.NodeTo))) == null)
                                Dependencies.Add(dependency2);                                                          //Add connection right
                        }
                        this.AttainableNodes.Add(i * M + j);
                    }
                    this.NumerableSchema[i, j] = i * M + j;
                }
                    #endregion
            #endregion
        }
 
 
 
        /// <summary>
        /// Returns unvisited nodes which is connected to parent node or null
        /// </summary>
        /// <param name="ParentNode">Parent Node</param>
        /// <param name="Dependencies">List of dependencies</param>
        /// <returns>List of unvisited nodes which is connected to parent node or null</returns>
        private List<int> GetUnvisitedChildNodes(int Parent)
        {
            List<int> result = new List<int>();
                List<Dependency> DependenciesFromParent = this.Dependencies.FindAll(dependency => dependency.NodeFrom == Parent);
                foreach (Dependency dependency in DependenciesFromParent)                
                    result.Add(dependency.NodeTo);
 
                List<Dependency> DependenciesToParent = this.Dependencies.FindAll(dependency => dependency.NodeTo == Parent);
                foreach (Dependency dependency in DependenciesToParent)
                    result.Add(dependency.NodeFrom);                
                return result;
        }
 
        public List<Path> SearchAllPaths(int NodeFrom, int NodeTo)
        {
            //Create new list of paths
            List<Path> FoundPaths = new List<Path>();
            Queue<Path> q = new Queue<Path>();
            Path path = new Path();
            path.Nodes.Add(NodeFrom);
            q.Enqueue(path);
            while (q.Any())                                                                                 //while queue isn't empty
            {
                Path tempPath = q.Dequeue();                                                                //Gets first path from queue
                List<int> childNodes = GetUnvisitedChildNodes(tempPath.Nodes[tempPath.Nodes.Count - 1]);    //Gets all children by last node of tempPath
                foreach (int child in childNodes)                                                           //For each child in children
                {
                    Path newPath = new Path();                                                              //Reset newPath
                    newPath = tempPath.CreateCopy();                                                    //Copy nodes from tempPath to new path
                    if (!newPath.Nodes.Contains(child))                                                     //Reset paths with cycles
                    {
                        newPath.Nodes.Add(child);                                                           //Increment pass with child
                        if (!q.Contains(newPath))
                        {
                            q.Enqueue(newPath);                                                             //Add newPath to the end of queue                
                            if (child == NodeTo &&
                                !FoundPaths.Contains(newPath))                                              //if  target path is found
                            {
                                FoundPaths.Add(newPath);                                                    //Add target path to List of paths
                            }
                        }
                    }
                }
            }
            return FoundPaths;
        }
 
    }
    
    public class Dependency
    {
        public int NodeFrom { get; set; }
        public int NodeTo { get; set; }
 
        public Dependency(int nodeFrom, int nodeTo)
        {
            this.NodeFrom = nodeFrom;
            this.NodeTo = nodeTo;
        }
 
        public override string ToString()
        {
            return (this.NodeFrom).ToString()
                    + " - " +
                   (this.NodeTo).ToString();
        }
    }
 
    public class Path
    {
        private List<int> nodes;
        public List<int> Nodes { get { return nodes; } set { nodes = value; } }
 
        public Path()
        {
            this.nodes = new List<int>();
        }
 
        public Path CreateCopy()
        {
            Path path = new Path();
            foreach (int node in this.nodes)
                path.Nodes.Add(node);
            return path;
        }
 
        public override string ToString()
        {
            string result = "";
            foreach (int node in this.nodes)
                result = result + node.ToString() + ", ";
            return result;
            
        }        
    }
}

using System;
using System.Collections.Generic;
 
namespace GraphSolution
{
    class Program
    {
        static void Main(string[] args)
        {
            Graph Castle = new Graph(
                   new int[5,10]{ {1,1,1,1,1,0,1,1,1,1},
                                  {1,0,1,0,1,0,1,1,0,0},
                                  {1,1,1,1,1,1,1,1,1,1},
                                  {0,1,0,1,0,1,0,1,0,1},
                                  {1,1,1,1,1,0,1,1,1,1} });
            //Output list of dependencies
            for (int i = 0; i < Castle.Dependencies.Count; i++)
                Console.WriteLine("{0,3} Connection {1}", i, Castle.Dependencies[i].ToString());
            Console.WriteLine();
            //Output AttainableNodes
            for (int i = 0; i < Castle.AttainableNodes.Count; i++)
                Console.Write("{0,3},",Castle.AttainableNodes[i].ToString());
            Console.WriteLine();
            Console.WriteLine();
            //Output Digital Schema
            DisplayArray(Castle.Schema);
            //Output NumerableSchema
            DisplayArray(Castle.NumerableSchema);
            Console.WriteLine();
            //Input nodes for finding
            int nodeFrom = 0;
            int nodeTo = 0;
            Console.WriteLine("Type number of node from which start path");
            int.TryParse(Console.ReadLine(), out nodeFrom);
            Console.WriteLine("Type number of node to which end path");
            int.TryParse(Console.ReadLine(), out nodeTo);
 
            //Output paths
            Console.WriteLine("Paths are found from {0} to {1} :",nodeFrom, nodeTo);
            List<Path> FoundPaths = Castle.SearchAllPaths(nodeFrom, nodeTo);
            for (int i = 0; i < FoundPaths.Count; i++)
                Console.WriteLine("{1} Path: {0}", FoundPaths[i].ToString(),i+1);
            Console.ReadLine();
        }
 
        private static void DisplayArray(int[,] Array)
        {
            Console.WriteLine();
            Console.WriteLine();
            //Output NumerableSchema
            for (int i = 0; i < Array.GetLength(0); i++)
            {
                string result = "";
                for (int j = 0; j < Array.GetLength(1); j++)
                {
                    result = result + string.Format("{0,4}", Array[i, j].ToString());
                }
                Console.WriteLine(result);
            }
        }
    }
}