#include <vector>
#include <fstream>
#include <iostream>
#include <cmath>

struct vi2d{
    int x,y;
    friend std::ostream&operator<<(std::ostream&out,vi2d&rhs){
        out<<"("<<rhs.x<<","<<rhs.y<<")";
        return out;
    }
};

struct node{
    private:
    char elevation='a';
    public:
    bool visited=false;
    std::vector<node*>connections;
    int myDist=INFINITY;
    vi2d pos;
    node*parent=nullptr;
    node(char elevation){
        this->elevation=elevation;
    };
    char getElevation(){
        return elevation=='S'?'a':elevation=='E'?'z'+1:elevation;
    }
};


vi2d playerPos={0,0};
vi2d endingPos={0,0};
std::vector<std::vector<node>>grid;
std::vector<node*>possibleStartingLocs;
node*startNode;
node *endNode;

int main()
{
	std::ifstream file("input");
    while (file.good()){
        std::string line;
        std::getline(file,line);
        std::vector<node>row;
        if (line.length()>0){
            for (int x=0;x<line.length();x++){
                row.push_back(node(line[x]));
                if (line[x]=='S'){
                    playerPos={x,(int)grid.size()};
                }
                if (line[x]=='E'){
                    endingPos={x,(int)grid.size()};
                }
            }
            grid.push_back(row);
        }
    }

    std::cout<<"================"<<std::endl;
    for (int y=0;y<grid.size();y++){
        for (int x=0;x<grid[y].size();x++){
            std::cout<<grid[y][x].getElevation();
            grid[y][x].pos={x,y};
            if (grid[y][x].getElevation()=='a'){
                possibleStartingLocs.push_back(&grid[y][x]);
            }
            if (x>0&&grid[y][x-1].getElevation()-1<=grid[y][x].getElevation()){
                grid[y][x].connections.push_back(&grid[y][x-1]);
            }
            if (x<grid[y].size()-1&&grid[y][x+1].getElevation()-1<=grid[y][x].getElevation()){
                grid[y][x].connections.push_back(&grid[y][x+1]);
            }
            if (y>0&&grid[y-1][x].getElevation()-1<=grid[y][x].getElevation()){
                grid[y][x].connections.push_back(&grid[y-1][x]);
            }
            if (y<grid.size()-1&&grid[y+1][x].getElevation()-1<=grid[y][x].getElevation()){
                grid[y][x].connections.push_back(&grid[y+1][x]);
            }
            if (x==playerPos.x&&y==playerPos.y){
                startNode=&grid[y][x];
                //std::cout<<"Starting node set."<<std::endl;
            }
            if (x==endingPos.x&&y==endingPos.y){
              endNode = &grid[y][x];
              //std::cout << "Ending node set." << std::endl;
            }
        }
        std::cout<<std::endl;
    }

    int bestPath=INFINITY;
    node*testNode;
    for (int l=0;l<possibleStartingLocs.size();l++){
        testNode=possibleStartingLocs[l];
        //std::cout<<"Checking location: "<<testNode->pos<<std::endl;
        for (int y=0;y<grid.size();y++){
            for (int x=0;x<grid[y].size();x++){
                node&n=grid[y][x];
                n.visited=false;
                n.myDist=INFINITY;
                n.parent=nullptr;
            }
        }
        std::vector<node*>searchNodes;
        searchNodes.push_back(testNode);
        testNode->myDist=0.0f;
        while (searchNodes.size()>0){
            node*currentNode=searchNodes.front();
            if (currentNode->visited){
                searchNodes.erase(searchNodes.begin());
                continue;
            }
            currentNode->visited=true;
            for (int i=0;i<currentNode->connections.size();i++){
                node*neighbor=currentNode->connections[i];
                if (!neighbor->visited){
                    searchNodes.push_back(neighbor);
                }
                float lowerGoal=currentNode->myDist+pow(neighbor->pos.x-currentNode->pos.x,2)+pow(neighbor->pos.y-currentNode->pos.y,2);
                if (lowerGoal<neighbor->myDist){
                    neighbor->parent=currentNode;
                    neighbor->myDist=lowerGoal;
                }
            }
        }
        node *searchNode = endNode;
        bool completed=false;
        int jumps=0;
        while (searchNode!=testNode){
            if (searchNode->parent!=nullptr){
                //std::cout<<"Node goes from "<<searchNode->pos<<" to "<<searchNode->parent->pos<<std::endl;
                jumps++;
                searchNode=searchNode->parent;
            }else{
                break;
            }
        }
        if (searchNode==testNode){
            if (jumps<bestPath){
                std::cout<<"New Shortest path is "<<jumps<<" hops"<<std::endl;
                bestPath=jumps;
            }
        }
    }

	return 0;
}