private static bool[,] InitMarked(int size)
        {
            bool[,] marked = new bool[size, size];
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                    marked[i, j] = false;
            }

            return marked;
        }

        // Checks if the cell at index [i,j] is already in the frontier
        private static bool Exists(List<(int, int)> frontier, int i, int j)
        {
            for (int index = 0; index < frontier.Count; index++)
            {
                if (frontier[index].Item1 == i && frontier[index].Item2 == j)
                    return true;
            }
            return false;
        }

        private static void Mark(bool[,] marked, List<(int, int)> frontier, int i, int j)
        {
            //TODO
            // Marks the cell [i, j] as visited and add its non visited neighbour to the frontier
            marked[i,j] = true;
            if (i> 0 && !marked[i-1,j] && !Exists(frontier,i-1,j))
            {
                frontier.Add((i-1,j));
            }
            if (j < marked.GetLength(0)-1 && !marked[i,j+1] && !Exists(frontier,i,j+1))
            {
                frontier.Add((i,j+1));
            }

            if (i < marked.GetLength(0)-1 && !marked[i+1,j] && !Exists(frontier,i+1,j))
            {
                frontier.Add((i+1,j));
            }
            if (j> 0 && !marked[i,j-1] && !Exists(frontier,i,j-1))
            {
                frontier.Add((i,j-1));
            }
        }

        private static Maze.Direction FindNeighbours(bool[,] marked, int i, int j)
        {
            //TODO
            // Finds the directions in which marked neighbours exists
            // Chooses one randomly and returns it
            // If none exists, return the NULL direction

            List<(int,int)> l = new List<(int,int)>();
            if (i>0 && marked[i-1,j])
            {
                l.Add((i-1,j));
            }
            if (j<marked.GetLength(0)-1 && marked[i,j+1])
            {
                l.Add((i,j+1));
            }
            if (i<marked.GetLength(0)-1 && marked[i+1,j])
            {
                l.Add((i+1,j));
            }
            if (j>0 && marked[i,j-1])
            {
                l.Add((i,j-1));
            }
            Random a = new Random();
            int b = a.Next(l.Count);
            int x = l[b].Item1;
            int y = l[b].Item2;
            if (x<i)
            {
                return Maze.Direction.NORTH;
            }
            else if (x>i)
            {
                return (Maze.Direction.SOUTH);
            }
            else if ( y> j)
            {
                return (Maze.Direction.EAST);
            }
            else if ( y< j)
            {
                return (Maze.Direction.WEST);
            }
            else
            {
                return Maze.Direction.NULL;
            }

        }

        public static Maze GenPrimMaze(int size)
        {

            //TODO
            // Generates a maze using Prim's algorithm:
            //    1. Choose a random cell
            //    2. Mark it and add its neighbours to the frontier
            //    3. Choose a random cell in the frontier and remove it from the frontier
            //    4. Carve path from this cell to an already marked cell
            //    5. Repeat from step 3 until nothing is left in the frontier
            Maze maze = new Maze(size);
            Random x = new Random();
            int i = x.Next(size );
            int j = x.Next(size );
            List<(int, int)> frontier = new List<(int, int)>();
            bool[,] marked = InitMarked(size);
            Mark(marked, frontier, i, j);
            while (frontier.Count > 0)
            {
                int g = x.Next(frontier.Count);
                int m = frontier[g].Item1;
                int n = frontier[g].Item2;

                maze.CarvePath(m, n, FindNeighbours(marked, m, n));
                Mark(marked, frontier, m, n);
                frontier.Remove((m, n));
            }

            return maze;
        }
    }