/*-------------------------------------------------------------------------
  Include files:
--------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
/*=========================================================================
  Constants and definitions:
==========================================================================*/

/* put your #defines and typedefs here*/
#define N 4


/*-------------------------------------------------------------------------
  The main program. (describe what your program does here)
 -------------------------------------------------------------------------*/
//void fillbeenthere(int beenthere[N][N],int start);
void PrintWelcomeMessage();
void PrintSourceCityMessage();
void PrintDestinationCityMessage();
void input_function(int matrix[N][N]);
int pathfinder(int matrix[N][N],int i, int sum,int beenthere[N],int *fullsum,int end,int path[9],int counter);


int main()
{
    int matrix[N][N] = {0};
    int beenthere[N] = {0};
    int path[9] = {-1,-1,-1,-1,-1,-1,-1,-1,-1};
    int start = 0, end = 0,finalsum = 0, *fullsum = &finalsum, sum = 0 ,k = 0,counter = 0;
    PrintWelcomeMessage();
    input_function(matrix);
    PrintSourceCityMessage();
    scanf(" %d",&start);
    PrintDestinationCityMessage();
    scanf(" %d",&end);
    //fillbeenthere(beenthere,start);
    finalsum = matrix[start][end];
    path[0] = start;
    beenthere[start] = 1;
    counter = pathfinder(matrix,start,sum,beenthere,fullsum,end,path,counter);
    for (int q = 0; q <= 8;q++)
    {
        printf("%d ",path[q]);
    }
    return 0;
}
void PrintWelcomeMessage()
{
    printf("Please enter road matrix:\n");
}

void PrintSourceCityMessage()
{
    printf("Please enter source city:\n");
}

void PrintDestinationCityMessage()
{
    printf("Please enter destination city:\n");
}

void input_function(int matrix[N][N])
{
    char temp = 0;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            scanf(" %c",&temp);
            if (temp != '\n')
            {
                matrix[i][j]=(int)temp-48;
            }
        }
    }
}
int pathfinder(int matrix[N][N],int i, int sum,int beenthere[N],int *fullsum,int end,int path[9],int counter)
{
    int kickback = 0;
    int temp = 0;
    printf("Starting pathfinder with counter=%d, sum=%d, fullsum = %d, counter = %d\n", i, sum, *fullsum, counter);
    //printf(" counter %d\n",counter);
    for(int j = 0; j < N; j++)
    {

        printf("Testing path for city: %d at level %d, path taken thus far [%d, %d, %d, %d] \n", j, counter, path[0], path[1], path[2], path[3]);

        if(beenthere[j] == 1)
        {
            printf("Aborted path towards city: %d due to already travelling at this city\n", j);
            //printf("been here j %d \n",j);
            continue;
        }
        if(sum + matrix[i][j] > *fullsum)
        {
            printf("Aborted path towards city: %d due to travel length (%d) greater than current minimum (%d) \n", j, sum + matrix[i][j], *fullsum);
            //printf("too big \n");
            continue;
        }
        //sum = matrix[i][j] + sum;
        beenthere[j] = 1;
        //printf("right before end\n");
        if(j==end)
        {
            //printf("in if end \n");
            if(matrix[i][j] + sum < *fullsum)
            {
                printf("Overriding the best-sum thus far (%d) with %d\n",*fullsum,  matrix[i][j] + sum);
                *fullsum = matrix[i][j] + sum;
                path[counter+1] = j;
                return counter+1;
            }
        }

        //printf("out if bad \n");
        //beenthere[i][j] = 1;
        temp = pathfinder(matrix,j,matrix[i][j] + sum,beenthere,fullsum,end,path,counter+1);
        beenthere[j] = 0;
        if(temp >= 0)
        {
            path[counter] = i;
            //return counter;
            kickback = temp;
        }
        else
        {
            kickback = kickback >=0 ? kickback : -1;
            printf("kick back %d \n",kickback);
        }
    }
    return kickback;
}
/*void fillbeenthere(int beenthere[N][N],int start)
{
    for (int i = 0;i < N;i++)
    {
        for(int j = 0;j < N; j++)
        {
            if (j == start)
            {
                beenthere[i][j] = 1;
            }

        }
        beenthere[i][i] = 1;
    }
}
*/