#define _CRT_SECURE_NO_WARNINGS

/*
READ THIS, AND THEN REPLACE THIS ENTIRE COMMENT WITH YOUR OWN
Replace everything here with an opening comment, in your own words,
describing the purpose of this program.  Include your name and ID
number in this comment.

By including your name in this file, you are confirming that you are
the author of the code that follows and that you have not copied code
from anyone else for this project.  Modifying, or making superficial
changes to someone else's code is not acceptable.  THIS IS IMPORTANT.
*/

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

#define MAX_COLS 100
#define MAX_ROWS 100

#define MAX_ROWS 100  // The maximum number of rows for any map
#define MAX_COLS 100  // The maximum number of cols for any map
#define MAX_VAL 10000 // The maximum number of positions in any map

#define FILENAME "map1.txt"  // The filename of the map

typedef struct {
	int col, row;
} Position;

typedef struct {
	Position Queue[10000];
	int size;
} List;

//Define functions:
void InitList(List *a);
void AddToList(List *a, Position point);
Position RemoveFromList(List *a);
int min(int a, int b);

/* Every function must begin with a comment, including this one */
int main(void)
{
	FILE *fp;
	int rows;
	int cols;
	char c;
	char map[MAX_COLS][MAX_ROWS];
	int distances[MAX_COLS][MAX_ROWS];
	List myList;
	int startx;
	int starty;
	int dist;
	int x = 0;
	int y = 0;
	Position pos, temp;

	fp = fopen(FILENAME, "r");

	if(fp == 0) {
		printf("Sorry, couldn't open file\n");
		return 0;
	}
	else {
		fscanf(fp, "%d", &rows);
		fscanf(fp, "%d", &cols);
	}

	while((c = fgetc(fp)) != EOF) {
		if(c == '@') {
			map[x][y] = c;
			distances[x][y] = 0;
			startx = x;
			starty = y;
			x++;
		}
		else if(c == ' ' || c == '*' || (c >= 'A' && c <= 'Z')) {
			map[x][y] = c;
			distances[x][y] = MAX_VAL;
			x++;
		}

		if(x == cols) {
			x = 0;
			y++;
		}
	}

	printf("Starting position = (%d,%d)\n", starty, startx);

	InitList(&myList);

	pos.col = startx;
	pos.row = starty;
	AddToList(&myList, pos);

	while(myList.size > 0) {
		pos = RemoveFromList(&myList);

		if(distances[pos.col][pos.row] != MAX_VAL && map[pos.col][pos.row] != '@') {
			continue;
		}

		//The distance to pos is (the minimum distance to any adjacent position) + 1
		if(map[pos.col][pos.row] != '@') {
			dist = min(min(min(distances[pos.col - 1][pos.row], distances[pos.col + 1][pos.row]), distances[pos.col][pos.row - 1]), distances[pos.col][pos.row + 1]) + 1;
			distances[pos.col][pos.row] = dist;
		}

		if(map[pos.col][pos.row] >= 'A' && map[pos.col][pos.row] <= 'Z') {
			printf("Distance to %c (%d,%d) = %d\n", map[pos.col][pos.row], pos.row, pos.col, distances[pos.col][pos.row]);
		}

		if(map[pos.col - 1][pos.row] != '*') {
			temp.col = pos.col - 1;
			temp.row = pos.row;
			AddToList(&myList, temp);
		}

		if(map[pos.col + 1][pos.row] != '*') {
			temp.col = pos.col + 1;
			temp.row = pos.row;
			AddToList(&myList, temp);
		}

		if(map[pos.col][pos.row - 1] != '*') {
			temp.col = pos.col;
			temp.row = pos.row - 1;
			AddToList(&myList, temp);
		}

		if(map[pos.col][pos.row + 1] != '*') {
			temp.col = pos.col;
			temp.row = pos.row + 1;
			AddToList(&myList, temp);
		}
	}

	return 0;
}

void InitList(List *a)
{
	a -> size = 0;
}

void AddToList(List *a, Position point)
{
	/*Point to the values array at the last position, and make this equal the input value*/
	a->Queue[a->size].row = point.row;
	a->Queue[a->size].col = point.col;
	/*Increase the size*/
	a->size++;
}

Position RemoveFromList(List *a)
{
	Position ret;
	/*Initialise variable i and set it to 0*/
	int i = 0;
	/*Set the *value pointer to = the first position in the size array*/
	ret = a->Queue[0];
	/*Create a for loop to cycle through the Queue array and shit each element to the left, then reduce the value of size*/
	for(i = 0; i < (a->size-1); i++) {
		a->Queue[i] = a->Queue[i+1];
	}
	a->size--;

	return ret;
}

int min(int a, int b)
{
	if(a < b) {
		return a;
	}
	else {
		return b;
	}
}