数据结构作业——链栈&迷宫求解

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <windows.h>
#include <conio.h>

#define MAZESIZE 15

typedef struct ElemType{
	int row;
	int col;
    int direction;
} PosType;

typedef struct {
	PosType pos;
    struct StackNode *next;
} StackNode;

typedef struct {
	StackNode *top;
	int stacksize;
} LinkStack;

char maze[MAZESIZE][MAZESIZE];
int FLAG = 1;

void gotoxy(int x, int y);
void InitMaze();
void DrawMaze();
bool InitStack(LinkStack **stack);
bool isEmpty(LinkStack *stack);
bool Push(LinkStack *stack, PosType e);
bool Pop(LinkStack *stack, PosType *e);
bool Pass(PosType curpos);
bool Mark(PosType curpos);
bool FindPath(PosType start, PosType end);
PosType NextPos(PosType curpos);

void gotoxy(int x,int y){
    HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);    //GetStdHandle函数获取一个指向特定标准设备的句柄，包括标准输入，标准输出和标准错误; STD_OUTPUT_HANDLE正是代表标准输出（也就是显示屏）的宏
    COORD pos;
    pos.X = x;
    pos.Y = y;
    SetConsoleCursorPosition(handle,pos);
}

void InitMaze(){
    time_t t;
    srand((unsigned)time(&t));
    system("cls");

    for (int i = 0; i <= MAZESIZE - 1; i++){
        for (int j = 0; j <= MAZESIZE - 1;j++){
            if (i==0 || j==0 || i==MAZESIZE-1 || j==MAZESIZE-1){
                maze[i][j] = '#';
            }else if((((rand()%13+1) == i) || ((rand()%13+1) == j)) && !(i==1 && j==1) && !(i==MAZESIZE-2 && j==MAZESIZE-2)){
                maze[i][j] = '#';
            }else{
                maze[i][j] = ' ';
            }
        }
    }
    printf("[*] init the maze success!");
}

void DrawMaze() {
    for (int i = 0;i < MAZESIZE;i++){
        printf("\n"); printf("\t");
        for (int j = 0;j < MAZESIZE;j++){
            printf("%c ", maze[i][j]);
        }
    }
}

bool InitStack(LinkStack **stack){
    *stack = (LinkStack *)malloc(sizeof(LinkStack));    // 注意要给链栈分配内存

    (*stack)->top = NULL;   // 链栈的空其实就是 top=NULL 的时候
	(*stack)->stacksize = 0;

    return true;
}

bool isEmpty(LinkStack *stack){
    return stack->stacksize == 0 ? true : false;
}

bool Push(LinkStack *stack, PosType e){
    StackNode *s = (StackNode *)malloc(sizeof(StackNode));

    s->pos = e;
	s->next = stack->top;   // 把当前的栈顶元素赋值给新结点的直接后继
	stack->top = s; // 将新的结点s赋值给栈顶指针
	stack->stacksize++;

	return true;
}

bool Pop(LinkStack *stack, PosType *e){
    StackNode  *p;

	if (isEmpty(stack)) return false;
	*e = stack->top->pos;
	p = stack->top; // p用来存储要删除的栈顶结点
	stack->top = stack->top->next;  // 使得栈顶指针下移一位，指向后一结点
	free(p);    // 释放结点p
	stack->stacksize--;

	return true;
}

bool Pass(PosType curpos){
    if(maze[curpos.row][curpos.col] == ' '){
        return true;
    }
    return false;
}

bool Mark(PosType curpos){
    maze[curpos.row][curpos.col] = '@';
    return true;
}

bool FindPath(PosType start, PosType end){
    LinkStack *stack;
    int curstep = 1;
    PosType curpos;
    curpos = start;

    if (InitStack(&stack)) printf("\n[*] int the stack success!\n");
    printf("[*] Start!\n", start.row, start.col);
    do{
        if(Pass(curpos)){
            Mark(curpos);
            curpos.direction = 1;
            Push(stack, curpos);
            gotoxy(0,0);
            DrawMaze();
            Sleep(500);
            if(curpos.row == end.row && curpos.col == end.col){
                printf("\n\n\n\n\n\n[*] reach the end: (%d, %d)\n", curpos.row, curpos.col);
                return true;
            }
            curpos = NextPos(curpos);
            curstep++;
            printf("\n\n[+] step: %d", curstep);
            printf("  -> (%d, %d)", curpos.row, curpos.col);
        }else{
            if(!isEmpty(stack)){
                Pop(stack, &curpos);
                while(curpos.direction == 4 && !isEmpty(stack)){
                    Mark(curpos);
                    Pop(stack, &curpos);
                    curstep--;
                    gotoxy(0, 0);
                    DrawMaze();
                    printf("\n\n\n[-] back to (%d, %d)", curpos.row, curpos.col);
                }
                if(curpos.direction < 4){
                    curpos.direction++;
                    Push(stack, curpos);
                    curpos = NextPos(curpos);
                }
            }
        }
    } while (!isEmpty(stack));
    printf("\n\n[!] sorry, can't find the path to end!\n");
    return false;
}

PosType NextPos(PosType curpos){
    switch(curpos.direction){
        case 1: curpos.col++; break;
        case 2: curpos.row++; break;
        case 3: curpos.col--; break;
        case 4: curpos.row--; break;
    }
    return curpos;
}

int main() {
    LinkStack *stack;
    PosType Start, End;
    char f;
    Start.row = 1; Start.col = 1;
    End.row = 13; End.col = 13;

    SetConsoleTitleA("Let's_Play_Mazes!");
    system("color 3E");
    system("mode con cols=45 lines=35");

    do{
        InitMaze();
        DrawMaze();
        FindPath(Start, End);
        printf("\n\n\n\n\n\n\n\n[*] another game? (y or n)\n");
        f = getchar();
        if(f=='n') FLAG = 0;
        else if(f == 'y'){
            system("cls");
        }
    } while (FLAG);
    getchar();
	return 0;
}