#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 40
#define scanf_s scanf

typedef struct egde {
	int pointA;
	int pointB;
}Edge;


int nodeID(int columns, int i, int j) {
	return i * columns + j;
}

void menu() {
	printf("1. kreiraj \n");
	printf("2. ispis\n");
	printf("3. \n");
	printf("4.  \n");
	printf("5.  \n");
	printf("6. \n");
	printf("7.  \n");
	printf("8. \n");
}

Edge **addEdges(Edge **edges, int *numOfEdges, int newNode, int i, int j, int rows, int columns) {
	edges = (Edge**)realloc(edges, (*numOfEdges +1) * 4 * sizeof(Edge*));
	if (i > 0) {
		Edge *up = (Edge*)malloc(sizeof(Edge));
		int pointB = nodeID(columns, i - 1, j);
		up->pointB = pointB;
		up->pointA = newNode;
		edges[*numOfEdges] = up;
		*numOfEdges+=1;
	}
	if (j > 0) {
		Edge *left = (Edge*)malloc(sizeof(Edge));
		int pointB = nodeID(columns, i, j - 1);
		left->pointB = pointB;
		left->pointA = newNode;
		edges[*numOfEdges] = left;
		*numOfEdges+=1;
	}
	if (i < columns - 1) {
		Edge *right = (Edge*)malloc(sizeof(Edge));
		int pointB = nodeID(columns, i, j + 1);
		right->pointB = pointB;
		right->pointA = newNode;
		edges[*numOfEdges] = right;
		*numOfEdges+=1;
	}
	if (j < rows - 1) {
		Edge *down = (Edge*)malloc(sizeof(Edge));
		int pointB = nodeID(columns, i + 1, j);
		down->pointB = pointB;
		down->pointA = newNode;
		edges[*numOfEdges] = down;
		*numOfEdges+=1;
	}
	return edges;
}

//int edgesEmpty(Edge *edges, int numOfEdges) {
//	int flag = 1;
//	for (int i = 0; i < numOfEdges * 4; i++)
//	{
//		Edge *n = malloc(sizeof(Edge));
//		*n = edges[i];
//		if (n->pointA != -1) {
//			flag = 0;
//		}
//	}
//	return flag;
//}

void print(int **mat, int rows, int columns) {
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < columns; j++)
		{
			if (mat[i][j] == 1)
				printf("#");
			else printf(" ");
		}
		printf("\n");
	}
}

void input(int **mat, int rows, int columns, int numOfNodes) {

	//int firstID, secondID;
	//vektor grana
	Edge **edges = calloc(0,sizeof(Edge*));
	//vektor cvorova
	int *nodes = (int*)calloc(numOfNodes, sizeof(int));
	//random generisi prvi cvor
	srand(time(0));
	int newNodeI = rand()%rows;//((double)rand() / (RAND_MAX + 1.0)) * rows;
	int newNodeJ = rand()%columns;//((double)rand() / (RAND_MAX + 1.0)) * columns;
	int newNode = nodeID(columns, newNodeI, newNodeJ);
	nodes[newNode] = 1;


	int numOfEdges = 0;
	while (1) {

		int usedNodes = 1;
		for (int i = 0; i < numOfNodes; i++) {
			if (nodes[i] == 0) {
				usedNodes = 0;
				break;
			}
		}
		if (usedNodes == 0) {
			edges = addEdges(edges, &numOfEdges, newNode, newNodeI, newNodeJ, rows, columns);
		}
		int edgeIndex;
		Edge *newEdge;

		while (1) {
			edgeIndex = rand()%numOfEdges;//((double)rand() / (RAND_MAX + 1.0)) * numOfEdges;
			newEdge = edges[edgeIndex];
			if (newEdge->pointA != -1) {
				break;
			}
		}

		int pointB = newEdge->pointB;
                int pointA = newEdge->pointA;
		if (!nodes[pointB]) {
			mat[pointA][pointB] = 1;
			mat[pointB][pointA] = 1;
			nodes[pointB] = 1;
		}
		newEdge->pointA = -1;
		newEdge->pointB = -1;

		newNode = pointB;
		newNodeJ = newNode % columns;
		newNodeI = newNode / columns;


		int flag = 1;
		for (int i = 0; i < numOfEdges; i++)
		{
			Edge *n;
			n = edges[i];
			if (n->pointA != -1) {
				flag = 0;
				break;
			}
		}
		if (flag == 1) break;
	}
}

int main() {

	int val, command;
	int rows, columns;
	int numOfNodes;



	menu();
	printf("upisi komandu: \n");
	scanf("%d", &command);
	while (command >= 1 && command <= 8) {
		switch (command) {
		case 1:
			printf("uneti broj vrsta i kolona\n");
			scanf("%d %d", &rows, &columns);
			numOfNodes = rows * columns;
			int **mat = malloc(numOfNodes * sizeof(int*));
			for (int i = 0; i < numOfNodes; i++) {
				mat[i] = calloc(numOfNodes,sizeof(int));
			}
			input(mat, rows, columns, numOfNodes);
			break;
		case 2: print(mat, rows, columns); break;
		case 3: break;
		case 4: break;
		case 5: break;
		case 6: break;
		case 7: break;

		}
		printf("upisi komandu: ");
		scanf("%d", &command);
	}

	scanf_s("%d", &val);
	return 0;
}