Najkrótsza droga do punktu w labirynice

Question

Witam, mam do zrobienia program który szczyta z pliku mapę, postaci

....

.#.#

....

i dla każdego punktu znajdzie najkrótszą drogę od lewego górnego rogu. Wynik ma zostać przedstawiony w postaci

0123

1#3#

2345

Największy problem jest w tym, że nauczyciel zasugerował mi utworzenie struktury, którą można a nawet trzeba zmodyfikować.

struct cell
{
struct cell * left_cell ;
struct cell * up_cell ;
struct cell * right_cell ;
struct cell * down_cell ;
int left_visited ;
int up_visited ;
int right_visited ;
int down_visited ;
char value ;
};

Komórki przechowują wskaźniki  do wszystkich 4 swoich sąsiadów. Ponadto wszystkie komórki są przechowywane w dwuwymiarowej tablicy (r * c) alokowanej dynamicznie. 

Potrafię stworzyć tę tablice, tylko wykorzystanie tej struktury i znalezienie najkrótszych ścieżek jest wyzwaniem nie do pokonania dla mnie

Comments

https://www.google.com/amp/s/www.geeksforgeeks.org/find-shortest-safe-route-in-a-path-with-landmines/amp/

https://www.google.com/amp/s/www.geeksforgeeks.org/c-program-for-dijkstras-shortest-path-algorithm-greedy-algo-7/amp/

---

mi się bardzo spodobał sposób tłumaczenia

https://www.youtube.com/watch?v=rop0W4QDOUI

---

@DragonCoder, Napisałem taki kod, ale z jakiegoś powodu nie działa. Na razie dałem sobie spokój z tą strukturą i zrobiłem inaczej

#include "stdafx.h"
#include "stdlib.h"

//Starting point
#define START_X 0
#define START_Y 0
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))

//example structure I have to use
struct Cell
{
	struct Cell *north;
	struct Cell *east;
	struct Cell *south;
	struct Cell *west;
	char value;
	int distance;


};


//function that prints a maze
void printMap(char **charMaze, int row, int col)
{

	for (int i = 0; i < row; i++)
	{


		for (int j = 0; j < col; j++)
		{
			printf_s("%c", charMaze[i][j]);
		}
		printf_s("\n");
	}

}
void printMap2(int **intMaze, int row, int col)
{

	for (int i = 0; i < row; i++)
	{


		for (int j = 0; j < col; j++)
		{
			printf_s("%d", intMaze[i][j]);
		}
		printf_s("\n");
	}

}


// functions that check if a point is valid
bool isValid(int x, int y, int row, int col)
{
	if (x < row && y < col && x >= 0 && y >= 0)
	{

		printf("Dobry punkt");
		return true;
	}
	else
	{
		printf("Nieprawidlowy");
	}

	return false;
}
bool isSafe(char **charMaze, int **visited, int x, int y)
{
	//char wall = '#';
	//char character = charMaze[x][y];
	if (charMaze[x][y] =='#' || visited[x][y])
	{

		printf("unsafe");
		return false;
	}
	else
	{
		printf("safe");
	}

	return true;
}
bool canGo(Cell *cell, int d)
{
	if (cell == NULL)
	{
		return 0;
	}
	if (cell->value == '#')
		return 0;
	if (cell->value == '.')
		return 1;
	if (cell->distance > d)
		return 1;

		return 0;
}




void findShortestPath(char **maze, int start_X, int start__Y, int i, int j, int row, int col, int **visited, int minDist, int dist)
{
	if (j = start__Y && i == start_X)
	{
		minDist = MIN(dist, minDist);
		return;
	}
	visited[start_X][start__Y] = 1;



	//bottom
	if (isValid(start_X + 1, start__Y, row, col) && isSafe(maze, visited, start_X + 1, start__Y))
		findShortestPath(maze, start_X + 1, start__Y, i, j, row, col, visited, minDist, dist + 1);
	//right
	if (isValid(start_X, start__Y + 1, row, col) && isSafe(maze, visited, start_X, start__Y + 1))
		findShortestPath(maze, start_X, start__Y + 1, i, j, row, col, visited, minDist, dist + 1);
	//top
	if (isValid(start_X - 1, start__Y, row, col) && isSafe(maze, visited, start_X + 1, start__Y))
		findShortestPath(maze, start_X + 1, start__Y, i, j, row, col, visited, minDist, dist + 1);
	//left
	if (isValid(start_X, start__Y - 1, row, col) && isSafe(maze, visited, start_X, start__Y - 1))
		findShortestPath(maze, start_X, start__Y - 1, i, j, row, col, visited, minDist, dist + 1);
	visited[start_X, start__Y] = 0;



}

int main()
{
	FILE *map;
	int start_X = 0;
	int start_Y = 0;
	int row, col;
	struct Cell cell;
	// I open a file with a maze
	fopen_s(&map, "test1.txt", "r");
	// I scan a row number and column number
	fscanf_s(map, "%d", &row);
	fscanf_s(map, "\n%d\n", &col);


	char** charMaze;
	charMaze = (char**)malloc(row * sizeof(char*));

	for (int i = 0; i < row; i++)
		charMaze[i] = (char*)malloc(col * sizeof(char));


	int** visited;
	visited = (int**)malloc(row * sizeof(int*));

	for (int i = 0; i < row; i++)
		visited[i] = (int*)malloc(col * sizeof(int));

	memset(visited, 0, sizeof visited);
	int minDist = INT_MAX;


	





	// I scan a maze and I put it in a array
	for (int i = 0; i < row; i++)
	{


		for (int j = 0; j < col; j++)
		{
			fscanf_s(map, "%c", &charMaze[i][j], 1);
		}
		fscanf_s(map, "\n");
	}

	findShortestPath(charMaze, start_X, start_Y, 2, 3, row, col, visited, minDist, 0);



	if (minDist != INT_MAX)
	{
		printf("Najkrotsza droga z poczatku do konca to %d", minDist);

	}
	else
	{
		printf("Nie da sie dojsc do punktu");
	}




	printMap(charMaze, row, col);
	
	
	
	fclose(map);














	return 0;

}