backtrack.c

#include <stdio.h>

typedef struct Pos {
	int x, y;
};

struct Pos put[100], minPut[100];
int n, lavirint[10][10], stX, stY, endX, endY, minBrojKoraka;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void Ispis(struct Pos putic[], int k) {
	for(int i = 1; i<=k;i++)printf("(%d, %d) ", putic[i].x, putic[i].y);
	printf("\n");
}

void Unos(){
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			scanf("%d", &lavirint[i][j]);
}

void Nadji(){
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++){
			if(lavirint[i][j] == 3){
				stX = i;
				stY = j;
			}else if(lavirint[i][j] == 2){
				endX = i;
				endY = j;
			}
		}
}

int MozeDaPredje(int x, int y){
	if(x >= 0 && x < n && y >= 0 && y < n && (lavirint[x][y] == 0 || lavirint[x][y] == 3 || lavirint[x][y] == 2)) return 1;
	else return 0;
}

void IdiNa(int k, int x, int y) {
	if(!MozeDaPredje(x, y)) return;
	lavirint[x][y] = -1;
	put[k].x = x;
	put[k].y = y;
	if(x == endX && y == endY){
		Ispis(put, k);
		if(k < minBrojKoraka){
			minBrojKoraka = k;
			for(int i = 1; i <= k; i++) minPut[i] = put[i];
		}
	}
	else for(int i = 0; i < 4; i++) {
		IdiNa(k + 1, x + dx[i], y + dy[i]);
	}

	lavirint[x][y] = 0;
}

void main() {
	minBrojKoraka = 100;
	printf("n = ");
	scanf("%d", &n);

	printf("Unesite elemente lavirinta\n");
	Unos();

	Nadji();

	IdiNa(0, stX, stY);

	if(minBrojKoraka == 100)
		printf("Gladan jadan");
	else {

		printf("Duzina je: %d", minBrojKoraka);
	}
}