#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define W 5
#define H 5

typedef struct p{
    char type;
    int x;
    int y;
    float distance;
}Point;

int square (int);
float root(double);
float distance(int, int, int, int);

int main() {

    Point grid[W][H];

    for (int i = 0; i < W; ++i) {
        for (int j = 0; j < H; ++j) {
            grid[i][j].type = 'x';
            grid[i][j].x = i;
            grid[i][j].y = j;
        }
    }

    Point start, end;

    srand(time(0));

    start.x = rand() % (4) + 1;
    start.y = rand() % (4) + 1;
    start.type = 's';
    end.x = rand() % (4) + 1;
    end.y = rand() % (4) + 1;
    end.type = 'e';

    grid[start.x][start.y] = start;
    grid[end.x][end.y] = end;

    float final_distance;
    float shortest_distance;
    Point nearest_point;
    Point reference_point = start;

    final_distance = distance(start.x, start.y, end.x, end.y);

    do{
        int x = reference_point.x;
        int y = reference_point.y;

        for (int i = -1; i < 1; i++) {
            for (int j = -1; j < 1; j++) {
                if(grid[x+i][y+i].type == 'e'){
                    printf("Finished!\n");
                    final_distance = 1;
                }
            }
        }
        if(final_distance != 1){
            shortest_distance = distance(reference_point.x, reference_point.y, end.x, end.y);
            for (int i = -1; i < 1; i++) {
                for (int j = -1; j < 1; j++) {
                    grid[x+i][y+j].distance = distance(grid[x+i][y+j].x, grid[x+i][y+j].y, end.x, end.y);
                    if (grid[x+i][y+j].distance < shortest_distance) {
                        shortest_distance = grid[x+i][y+j].distance;
                        nearest_point = grid[x+i][y+j];
                    }
                }
            }
            reference_point = nearest_point;
            grid[reference_point.x][reference_point.y].type = 'o';
        }

    }while(final_distance != 1);

    for (int k = 0; k < H; k++) {
        for (int i = 0; i < W; i++) {
            printf("%c ", grid[k][i].type);
        }
        printf("\n");
    }


    return 0;
}

int square(int x){
    return x*x;
}
float root(double x){
    return sqrt((double)x);
}
float distance(int x1, int y1, int x2, int y2){
    return root(square(x1-x2) + square(y1-y2));
}