苗火 Nicholas

[Data structures]Maze

2019-8-30 萧 写技术

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


#define MAX_STACK 1024
#define MAX 11

typedef struct _PosType{
	int x,y;
}PosType;

typedef struct _SElemType{
	int ord;
	PosType seat;
	int di;
}SElemType;

typedef struct _MazeType{
	int matrix[MAX][MAX];
	int m,n;
}MazeType;



typedef struct _SqStack{
	SElemType *base;
	SElemType *top;
	int stackSize;
}SqStack;

int InitStack(SqStack *S)
{
	S->base = (SElemType *)malloc(MAX_STACK*sizeof(SElemType));
	S->top = S->base;
	S->stackSize = MAX_STACK;	
	return 1;
}

int GetTop(SqStack *S, SElemType *e)
{
	if(S->top == S->base){
		return 0;
	}else{
		*e = *(S->top - 1);
		return 1;
	}
}

int Push(SqStack *S, SElemType e)
{
	if(S->top - S->base >= S->stackSize){
		return 0;
	}
	*(S->top++) = e;
}

int Pop(SqStack *S, SElemType *e)
{
	if(S->top == S->base){
		return 0;
	}else{
		*e = *(--S->top);
		return 1;
	}
}

int StackEmpty(SqStack *S)
{
	if(S->top == S->base){
		return 1;
	}else{
		return 0;
	}
}

int ClearStack(SqStack *S)
{
	S->top = S->base;
	return 1;
}

int PrintStack(SqStack *S)
{
	MazeType m;
	int i,j;
	m.m = 10;
	m.n = 10;
	for(i=0; i<m.m; i++){
		for(j=0; j<m.n; j++){
			m.matrix[i][j] = 0;
		}
	}
	

	SElemType *p = S->base;
	while(p != S->top){
		printf("(%d,%d) ", p->seat.x, p->seat.y);
		m.matrix[p->seat.x][p->seat.y] = 1;
		p++;
	}
	printf("\n");

	for(i=0; i<m.m; i++){
		for(j=0; j<m.n; j++){
			printf(" %d", m.matrix[i][j]);
		}
		printf("\n");
	}
	return 1;
}

int MazePath(MazeType maze, PosType start, PosType end)
{
	SqStack S;
	PosType curpos = start;
	InitStack(&S);
	SElemType e;
	e.ord = 0;

	do{
		if(maze.matrix[curpos.x][curpos.y] == 1){
			maze.matrix[curpos.x][curpos.y]++;//Footprint

			e.ord++;	
			e.seat = curpos;
			e.di = 1; //1-4  east, south, west, north
			Push(&S, e);

			if(curpos.x == end.x && curpos.y == end.y){
				printf(" Found path.\n");
				PrintStack(&S);
				return 1;
			}else{
				curpos.y++;
			}
		}else{
			/* Update the top element, 
			 * in order to turn to its next direction. */

			Pop(&S, &e);	
			while(e.di==4 && !StackEmpty(&S)){
				maze.matrix[e.seat.x][e.seat.y] = 0;
				Pop(&S, &e);
			}
			if(e.di<4){
				e.di++;
				Push(&S, e);
				switch(e.di){
					case 1:
						e.seat.y++;
						break;
					case 2:
						e.seat.x++;
						break;
					case 3:
						e.seat.y--;
						break;
					case 4:
						e.seat.x--;
						break;
				}
				curpos = e.seat;
			}

		}
		
	}while(!StackEmpty(&S));
	printf(" No path.\n");
	return 0;
}

void main()
{
	MazeType maze;
	PosType start,end;
	int i,j,c;

	printf("log.anycle.com\n\n");
	printf("Original data:\n");
	scanf(" %d %d", &maze.m, &maze.n);
	for(i=0; i<maze.m; i++){
		for(j=0; j<maze.n; j++){
			scanf(" %d", &c);
			maze.matrix[i][j] = c;
		}
	}	
	scanf(" %d %d", &start.x, &start.y);
	scanf(" %d %d", &end.x, &end.y);

	for(i=0; i<maze.m; i++){
		for(j=0; j<maze.n; j++){
			printf(" %d", maze.matrix[i][j]);
		}	
		printf("\n");
	}
	printf("Start:(%d, %d), End:(%d, %d).\n", 
			start.x, start.y, end.x, end.y );

	printf("Maze path:\n");
	MazePath(maze, start, end);

}

标签: Data Structures data_structures