using System;

using System.Collections.Generic;

​

class AStarSolver

{

    static int[,] maze = {

        { 0, 1, 0, 0, 0 },

        { 0, 1, 0, 1, 0 },

        { 0, 0, 0, 1, 0 },

        { 1, 1, 0, 1, 0 },

        { 0, 0, 0, 1, 0 }

    };

​

    static int N = 5; // Size of the maze

    static (int, int)[] directions = { (0, 1), (1, 0), (0, -1), (-1, 0) }; // right, down, left, up

​

    class Node : IComparable<Node>

    {

        public int X { get; set; }

        public int Y { get; set; }

        public int G { get; set; } // Cost from start to this node

        public int H { get; set; } // Heuristic cost (Manhattan distance to the goal)

        public int F => G + H; // Total cost

​

        public Node Parent { get; set; } // Parent node for path reconstruction

​

        public Node(int x, int y, int g, int h, Node parent = null)

        {

            X = x;

            Y = y;

            G = g;

            H = h;

            Parent = parent;

        }

​

        public int CompareTo(Node other) => F.CompareTo(other.F);

    }

​

    static int Heuristic(int x, int y, int goalX, int goalY)

    {

        // Manhattan distance heuristic

        return Math.Abs(x - goalX) + Math.Abs(y - goalY);

    }

​

    static List<(int, int)> AStarSolve(int startX, int startY, int goalX, int goalY)

    {

        var openList = new SortedSet<Node>(); // Priority queue, sorted by f(n)

        var closedList = new HashSet<(int, int)>(); // Visited nodes

        var startNode = new Node(startX, startY, 0, Heuristic(startX, startY, goalX, goalY));

​

        openList.Add(startNode);

​

        while (openList.Count > 0)

        {

            // Get node with the smallest f(n) value

            var currentNode = openList.Min;

            openList.Remove(currentNode);

​

            if (currentNode.X == goalX && currentNode.Y == goalY)

            {

                // Goal reached, reconstruct path

                return ReconstructPath(currentNode);

            }

​

            closedList.Add((currentNode.X, currentNode.Y));

​

            foreach (var direction in directions)

            {

                int newX = currentNode.X + direction.Item1;

                int newY = currentNode.Y + direction.Item2;

​

                if (IsValid(newX, newY) && !closedList.Contains((newX, newY)))

                {

                    int newG = currentNode.G + 1; // Cost to reach the neighbor

                    int newH = Heuristic(newX, newY, goalX, goalY);

                    var neighbor = new Node(newX, newY, newG, newH, currentNode);

​

                    // Add the neighbor to the open list

                    openList.Add(neighbor);

                }

            }

        }

​

        return null; // No solution

    }

​

    static List<(int, int)> ReconstructPath(Node node)

    {

        var path = new List<(int, int)>();

        while (node != null)

        {

            path.Add((node.X, node.Y));

            node = node.Parent;

        }

        path.Reverse();

        return path;

    }

​

    static bool IsValid(int x, int y)

    {

        return x >= 0 && x < N && y >= 0 && y < N && maze[x, y] == 0;

    }

​

    static void Main()

    {

        var path = AStarSolve(0, 0, N - 1, N - 1);

​

        if (path != null)

        {

            Console.WriteLine("Path found:");

            foreach (var (x, y) in path)

            {

                Console.WriteLine($"({x}, {y})");

            }

        }

        else

        {

            Console.WriteLine("No solution exists.");

        }

    }

}

​