using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    private static readonly string[] MAP = {

        "#########################################",

        "#   #       #     #           #         #",

        "# # # ### # # ### # ####### ### ####### #",

        "# #S#   # #   #   # #     #           # #",

        "# ##### # ######### # # ############# # #",

        "# #     # #         # #       #   #   # #",

        "# # ##### # ######### ##### # # # # ### #",

        "# #     #   #     #     #   # # # # # # #",

        "# ##### ######### # ##### ### # # # # # #",

        "#   #           #   #     #   # # #   # #",

        "# ### ######### # ### ##### ### # ##### #",

        "#   #   #     # # #   #       # #       #",

        "# # ### # ### # ### ### ####### ####### #",

        "# #     # #   #     #   # #     #     # #",

        "# ####### # ########### # # ##### # ### #",

        "#     # # #   #       #   # #   # #     #",

        "##### # ##### # ##### ### # ### # #######",

        "#   # #     # #   #   #   # #   #     # #",

        "# ### ### ### ### # ### ### # ####### # #",

        "#   #     #   #   # #   #   # #     #   #",

        "### ##### # ### ### ### # ### # ### ### #",

        "#       # #   # # #   # # #   # # #     #",

        "# ####### ### # # ### ### # ### # #######",

        "#       #   #   #   # #   #     #       #",

        "# ##### ### ##### # # # ##### ### ### ###",

        "#   # # #   #     # # #     # #     #   #",

        "### # # # ### # ##### # ### # # ####### #",

        "# #   #   #   # #     #   # # # #     # #",

        "# ### ##### ### # ##### ### # # # ### # #",

        "#   #       #   # # #   #   # # #   #   #",

        "# # ######### ### # # ### ### # ### #####",

        "# #     #   # # # #   #   # # #   #     #",

        "# ##### # # # # # ### # ### # ######### #",

        "# #   # # # # # #   # #   #             #",

        "# # # # # # # # ### ### # ############# #",

        "# # #     # # #   #   # #       #       #",

        "# ######### # # # ### ### ##### # #######",

        "#     #     # # #   #   # #     # #     #",

        "# ### ####### ### # ### ### ##### # ### #",

        "#   #             #   #     #       #E  #",

        "#########################################"

    };

    private static readonly int ROWS = MAP.Length;

    private static readonly int COLS = MAP[0].Length;

    private static readonly int NODES = ROWS * COLS;

    public static void Main()

    {

        // Construct graph from map.

        bool[,] neighbors = CreateNeighborGraph();

        int start = Find('S');

        int end = Find('E');

       Tuple<int, IEnumerable<int>> path = AStar.Find(

            (c) => Enumerable.Range(0, NODES).Where((n) => neighbors[c, n]), // Neighbors

            (c, n) => (neighbors[c, n] ? 1 : int.MaxValue), // Real Distance

            ManhattanDistance, // Distance Heuristic

            start, end, NODES);

        string[] newMap = new string[ROWS];

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

            newMap[i] = MAP[i];

        foreach(int node in path.Item2)

            if (newMap[node / COLS][node % COLS] == ' ')

                newMap[node / COLS] = newMap[node / COLS].Remove(node % COLS, 1).Insert(node % COLS, "*");

        Console.WriteLine("Start to end in {0} steps:", path.Item1);

        foreach(string row in newMap)

            Console.WriteLine(row);

    }

    private static bool[,] CreateNeighborGraph()

    {

        bool[,] neighbors = new bool[NODES, NODES];

        for(int r = 0; r < ROWS; ++r)

        {

            for(int c = 0; c < COLS; ++c)

            {

                if (MAP[r][c] == '#')

                    continue;

                int index = ToNode(r, c);

                if (r > 0 && MAP[r - 1][c] != '#')

                    neighbors[index, ToNode(r - 1, c)] = true;

                if (r < (ROWS - 1) && MAP[r + 1][c] != '#')

                    neighbors[index, ToNode(r + 1, c)] = true;

                if (c > 0 && MAP[r][c - 1] != '#')

                    neighbors[index, ToNode(r, c - 1)] = true;

                if (c < (COLS - 1) && MAP[r][c + 1] != '#')

                    neighbors[index, ToNode(r, c + 1)] = true;

            }

        }

        return neighbors;

    }

    private static int ToNode(int row, int col) {

        return row * COLS + col;

    }

    private static int Find(char s) {

        for(int r = 0; r < ROWS; ++r)

            for(int c = 0; c < COLS; ++c)

                if (MAP[r][c] == s)

                    return ToNode(r, c);

        return -1;

    }

    private static int ManhattanDistance(int start, int end) {

        int startRow = start / COLS;

        int startCol = start % COLS;

        int endRow = end / COLS;

        int endCol = end % COLS;

        return Math.Abs(startRow - endRow) + Math.Abs(startCol - endCol);

    }

}

​

public static class AStar

{

    private static readonly int NOT_VISITED = -1;

​

    private class DistanceComparer : IComparer<int>

    {

        private readonly int target;

        private readonly Func<int, int, int> distanceHeuristic;

        public DistanceComparer(int target, Func<int, int, int> distanceHeuristic)

        {

            this.target = target;

            this.distanceHeuristic = distanceHeuristic;

        }

​

        public int Compare(int left, int right)

        {

            int distance = this.distanceHeuristic(left, target) - this.distanceHeuristic(right, target);

            return (distance != 0) ? distance : left - right;

        }

    }

​

    public static Tuple<int, IEnumerable<int>> Find(

        Func<int, IEnumerable<int>> getNeighbors,

        Func<int, int, int> getDistance,

        Func<int, int, int> distanceHeuristic,

        int start, int goal, int nodeCount)

    {

        BitArray closed = new BitArray(nodeCount);

        SortedSet<int> open = new SortedSet<int>(new DistanceComparer(goal, distanceHeuristic));

        int[] previous = new int[nodeCount];

        int[] score = new int[nodeCount];

​

        for(int node = 0; node < nodeCount; ++node)

        {

            previous[node] = NOT_VISITED;

            score[node] = int.MaxValue;

        }

        score[start] = 0;

​

        open.Add(start);

        while(open.Count > 0)

        {

            int current = open.First();

            if (current == goal)

                return new Tuple<int, IEnumerable<int>>(score[current], ReconstructPath(current, previous));

​

            open.Remove(current);

            closed[current] = true;

            foreach(int neighbor in getNeighbors(current))

            {

                if (closed[neighbor]) continue;

​

                int tentativeScore = score[current] + getDistance(current, neighbor);

                if (!open.Contains(neighbor) || tentativeScore < score[neighbor])

                {

                    previous[neighbor] = current;

                    score[neighbor] = tentativeScore;

                    open.Add(neighbor);

                }

            }

        }

​

        return new Tuple<int, IEnumerable<int>>(-1, Enumerable.Empty<int>());

    }

​

    private static IEnumerable<int> ReconstructPath(int current, int[] previous)

    {

        yield return current;

        while(previous[current] != NOT_VISITED) {

            current = previous[current];

            yield return current;

        }

    }

}