G3. Teleport maze

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace Maze
{
    class Program
    {
        static void Main()
        {
            // 'S' - начальная точка, 'E' - конечная точка, 'X' - стена, 'T' - телепорт
            string[] maze =
            {
                "SX   X    ",
                " X XXXXX X",
                "     TX   ",
                "XXXX XXX X",
                "  T      X",
                " XXX XXXTX",
                " X       E"
            };

            var shortestPath = FindShortestPath(maze).Reverse().ToList();

            foreach (var point in shortestPath)
                Console.WriteLine($"({point.X}, {point.Y})");
        }

        public static IEnumerable<Point> FindShortestPath(string[] maze)
        {
            var elements = FindElements(maze);
            var start = elements['S'].First();
            var end = elements['E'].First();
            var teleports = elements.ContainsKey('T') ? elements['T'] : null;

            if (!elements.ContainsKey('S')) throw new ArgumentException("The maze does not have a start");
            if (!elements.ContainsKey('E')) throw new ArgumentException("The maze does not have an end");

            var queue = new Queue<Point>();
            var visited = new HashSet<Point>();
            var parents = new Dictionary<Point, Point>();

            queue.Enqueue(start);
            visited.Add(start);
            while (queue.Count != 0)
            {
                var currentPosition = queue.Dequeue();

                if (currentPosition == end)
                {
                    yield return currentPosition;
                    while (currentPosition != start)
                    {
                        currentPosition = parents[currentPosition];
                        yield return currentPosition;
                    }
                    break;
                }

                for (var dx = -1; dx <= 1; dx++)
                for (var dy = -1; dy <= 1; dy++)
                {
                    if (dx != 0 && dy != 0) continue;
                    var nextPosition = new Point(currentPosition.X + dx, currentPosition.Y + dy);
                    if (!CouldBeNewPoint(nextPosition, maze, visited)) continue;

                    visited.Add(nextPosition);
                    queue.Enqueue(nextPosition);
                    parents[nextPosition] = currentPosition;
                }

                if (teleports?.Count > 0 && teleports.Contains(currentPosition))
                {
                    foreach (var teleportPair in teleports)
                    {
                        if (teleportPair != currentPosition && CouldBeNewPoint(teleportPair, maze, visited))
                        {
                            visited.Add(teleportPair);
                            queue.Enqueue(teleportPair);
                            parents[teleportPair] = currentPosition;
                        }
                    }
                }
            }
        }

        private static bool CouldBeNewPoint(Point point, string[] maze, HashSet<Point> visited)
        {
            var height = maze.Length;
            var width = maze[0].Length;
            return point.X >= 0 && point.X < width &&
                   point.Y >= 0 && point.Y < height &&
                   maze[point.Y][point.X] != 'X' &&
                   !visited.Contains(point);
        }

        private static Dictionary<char, List<Point>> FindElements(string[] maze)
        {
            var elementAndPositions = new Dictionary<char, List<Point>>();
            for (var y = 0; y < maze.Length; y++)
            for (var x = 0; x < maze[y].Length; x++)
            {
                var currentPosition = maze[y][x];
                if (!elementAndPositions.ContainsKey(currentPosition))
                    elementAndPositions[currentPosition] = new List<Point>();
                elementAndPositions[currentPosition].Add(new Point(x, y));
            }
            return elementAndPositions;
        }
    }
}