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

using namespace std;

struct Point {
    int r, c;
    char sym;
    int id;
};

struct Place {
    int id;
    string n;
};

double dist(double cc, double cr, double pc, double pr){
    double x, y, d;
    x = pow((cc-pc),2);
    y = pow((cr-pr),2);
    d = pow(x+y, 0.5);
    return d;
}

int findAP(vector <int> v, double n){
    int s = 1;
    for(int i = 0; i<v.size(); i++){
        if (v.at(i) == n){
            s = 0;
        }
    }
    return s;
}

int main(){
    https://declaring variables

    string locfile;
    string namfile;
    double gr, gc, sr, sc, er, ec;
    Point p;
    vector <Point> data (1);
    double n = 0;
    int i, j;
    Place pl;
    int y,z;
    vector <Place> names (0);
    double cx, cy;
    double mind = -1, potd;
    double nx, ny;
    Point npoint, cpoint;
    int index;
    int cid, idi;
    vector <int> useddata (0);


    https://getting file names
    cout<<"Enter Locations Filename: "<<endl;
    getline(cin,locfile);

    cout<<"Enter Names Filename: "<<endl;
    getline(cin,namfile);

    https://opening files and checking for failure
    ifstream inloc;
    inloc.open(locfile.c_str());
    ifstream innam;
    innam.open(namfile.c_str());
    if (inloc.fail() or innam.fail()){
        cout<<"Input file could not be opened"<<endl;
        exit(EXIT_FAILURE);
    }

    https://reading location file
    inloc>>gr>>gc>>sr>>sc>>er>>ec;

    https://creating grid
    vector <char> row (gc,'.');
    vector < vector <char> > grid (gr, row);

    https://placing starting and ending points
    grid.at(sr-1).at(sc-1) = 'S';
    grid.at(er-1).at(ec-1) = 'E';

    https://reading in safe point information
    inloc>>p.r>>p.c>>p.sym>>p.id;
    if (p.r > gr or p.c > gc or p.r<=0 or p.c<=0){
        cout<<p.id<<" out of bounds - ignoring"<<endl;
        n = 1;
    }
    else {
        data.at(0) = p;
        grid.at(p.r-1).at(p.c-1) = p.sym;
    }
    inloc>>p.r;
    while (! inloc.fail()){
        inloc>>p.c>>p.sym>>p.id;
        if (p.r > gr or p.c > gc or p.r<=0 or p.c<=0){
            cout<<p.id<<" out of bounds - ignoring"<<endl;
        }
        else {
            if (n){
                data.at(0) = p;
                n=0;
            }
            else {
                data.push_back(p);
                grid.at(p.r-1).at(p.c-1) = p.sym;
            }
        }
        inloc>>p.r;
    }

    https://starting output
    ofstream omap("journey.txt");

    https://printing map
    for (i=0;i<grid.size();i++){
        for(j=0;j<grid.at(i).size();j++){
            omap<<grid.at(i).at(j);
        }
        omap<<endl;
    }

    https://reading in place names and correcting names
    innam>>pl.id;
    while (! innam.fail()){
        innam>>pl.n;
        z = pl.n.find("XX");
        while (z != pl.n.npos){
            pl.n.erase(z, 2);
            z = pl.n.find("XX");
        }
        y = pl.n.find("_");
        while (y != pl.n.npos){
            pl.n.erase(y,1);
            pl.n.insert(y," ");
            y = pl.n.find("_");
        }
        names.push_back(pl);
        innam>>pl.id;
    }

    https://continuing output
    omap<<"Start at "<<sr<<" "<<sc<<endl;


    https://processing data and values
    cx = sc;
    cy = sr;

    https://main loop to pick next point
    while (useddata.size()<data.size()){
        for(i = 0; i<data.size(); i++){
            potd = dist(cx, cy, data.at(i).c, data.at(i).r);
            if (mind == -1 and findAP(useddata,data.at(i).id)){
                nx = data.at(i).c;
                ny = data.at(i).r;
                npoint = data.at(i);
                index = i;
                idi = data.at(i).id;
                mind = potd;
            }
            else if (potd < mind and findAP(useddata,data.at(i).id)){
                nx = data.at(i).c;
                ny = data.at(i).r;
                npoint = data.at(i);
                index = i;
                idi = data.at(i).id;
                mind = potd;

            }
            else if (potd == mind and findAP(useddata,data.at(i).id)){
                if (data.at(i).id < npoint.id){
                    nx = data.at(i).c;
                    ny = data.at(i).r;
                    npoint = data.at(i);
                    index = i;
                    idi = data.at(i).id;
                    mind = potd;
                }

            }
        }
        https://outputs next point to report
        cx = nx;
        cy = ny;
        cpoint = npoint;
        useddata.push_back(idi);
        for (i = 0; i<names.size(); i++){
            if (idi == names.at(i).id){
                cid = i;
            }
        }
        omap<<"Go to "<<names.at(cid).n<<" at "<<cy<<" "<<cx<<endl;
        mind = -1;
    }

    https://final output
    omap<<"End at "<<er<<" "<<ec<<endl;

    https://closing input and output streams
    omap.close();
    innam.close();
    inloc.close();

    return 0;
}