[데이터 구조] 간단 한 미로 (재 귀적 으로 실현)

#pragma once 

#include"stack.h"

#include 
#include 
#include 
#include 
#include

#define MAX_ROW 4
#define MAX_COL 4

typedef struct Position
{
	int _x;
	int _y;

}Position;  

typedef struct Maze
{
	int _map[MAX_ROW][MAX_COL];

}Maze;  


//     
void InitMaze(Maze* m, int map[][MAX_COL]);

//         
int IsValidEntry(Maze* m, Position entry);

//        
int IsPass(Maze* m, Position cur);

//       
int IsExit(Maze* m, Position cur, Position entry);

//         
int _PassMaze(Maze* m, Position entry, Position cur, Stack* s);

//              ，             ：         ，         
void PassMaze(Maze* m, Position entry, Stack* s);

//    
void PrintMaze(Maze* m, int map[][MAX_COL]);

#include"Maze.h"
#include"stack.h"

//     
void InitMaze(Maze* m, int map[][MAX_COL])
{
	assert(&m);
	int i = 0;
	for (; i < MAX_ROW; i++)
	{
		int j = 0;

		for (; j < MAX_COL; j++)
		{

			m->_map[i][j] = map[i][j];


		}


	}
}

//       
int IsValidEntry(Maze* m, Position entry)
{
	assert(m);
	if ((entry._x == 0 || entry._y == 0) ||
		(entry._x == MAX_ROW - 1 || entry._y == MAX_COL - 1) &&
		(m->_map[entry._x][entry._y] == 1))

		return 1;
	return 0;


}


//        
int IsPass(Maze* m, Position cur)
{

	assert(m);

	if ((cur._x >= 0 && cur._x <= MAX_ROW - 1) &&
		(cur._y >= 0 && cur._y <= MAX_COL - 1) &&
		(m->_map[cur._x][cur._y] == 1))

		return 1;

	return 0;


}


int IsExit(Maze* m, Position cur, Position entry)
{

	assert(m);

	if ((entry._x == 0 || entry._y == 0) ||
		(entry._x == MAX_ROW - 1 || entry._y == MAX_COL - 1) &&
		(m->_map[entry._x][entry._y] == 1) &&
		(entry._x != cur._x) && (entry._y != cur._y))

		return 1;

	return 0;


}


//         
int _PassMaze(Maze* m, Position entry, Position cur, Stack* s)
{
	assert(m);
	assert(s);

	Position next;

	if (IsPass(m, cur))          //       
	{
		StackPush(s, cur);       //   

		if (IsExit(m, cur, entry))  //       
		{
			m->_map[cur._x][cur._y] = 2;  //              2
			return 1;
		}

		m->_map[cur._x][cur._y] = 2;     //          2




		//1.   

		next = cur;        //      


		next._x -= 1;      //   

	

		if (_PassMaze(m, entry, next, s));  //        

		   return 1;

		   

		//2.   
		next = cur;        //      

		next._y -= 1;      //   


		if (_PassMaze(m, entry, next, s));  //        

		   return 1;

		 

		//3.   
		next = cur;        //      

		next._y += 1;      //   
		
	
		if (_PassMaze(m, entry, next, s));  //        

		    return 1;


		//4.   
		next = cur;        //      

		next._x += 1;      //   

		if (_PassMaze(m, entry, next, s));  //        

		    return 1;

		//          3    
		m->_map[cur._x][cur._y] = 3;

		StackPop(s);
	}

	return 0;
}


//              ，             ：         ，         
void PassMaze(Maze* m, Position entry, Stack* s)
{
	assert(m);
	assert(s);

	if (!IsValidEntry(m, entry))       //     
	{
		printf("     !!!!
");

		return;
	
	}
	
	//    

	_PassMaze(m, entry,entry,s);


}



//    
void PrintMaze(Maze* m, int map[][MAX_COL])
{
	assert(m);

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

		int j = 0;
		for (; j < MAX_COL; j++)
		{

			printf("%d  ", m->_map[i][j]);

		}
		printf("
");
	}
	printf("
");
}

#include"Maze.h"
#include"stack.h"

void TestMaze()
{
	Stack s;
	Position entry;
	Maze m;
	StackInit(&s,10);


	int map[4][4] = {
		{0,0,0,0},
		{0,1,0,0},
		{0,1,1,1},
		{0,1,0,0}
	};

	InitMaze(&m, map);
	PrintMaze(&m, map);
	entry._x = 3;
	entry._y = 1;
	PassMaze(&m, entry,&s);      //        

	printf("
");

	PrintMaze(&m, map);


}


int main()
{

	Stack s;

	TestMaze();

	system("pause");
	return 0;
}