数据结构(C语言版)迷宫求解问题

/******************************************************************************* 该源文件用于操作栈的基本方法实现迷宫求解的问题 预估计只需要以下方法：1.用于根据curr_block的seat与ord得出next_block的坐标 2.用于求出迷宫路径，初步估计是一个循环 3.初始化代表迷宫的二维数组，用于标志那些通道块是"墙" 4.创建起点通道块和终点通道块 *******************************************************************************/ #include<stdlib.h> #include "status.h" #include "contents.h" #include "mazeoperation.h" /******************************************************************************* init_maze：初始化代表迷宫的二维数组 *******************************************************************************/ void init_maze(void) { int i, j; for(i = 0; i < 10; i++){ maze[0][i] = EXIST; maze[9][i] = EXIST; maze[i][0] = EXIST; maze[i][9] = EXIST; } maze[1][3] = EXIST; maze[1][7] = EXIST; maze[2][3] = EXIST; maze[2][7] = EXIST; maze[3][5] = EXIST; maze[3][6] = EXIST; maze[4][2] = EXIST; maze[4][3] = EXIST; maze[4][4] = EXIST; maze[5][4] = EXIST; maze[6][2] = EXIST; maze[6][6] = EXIST; maze[7][2] = EXIST; maze[7][3] = EXIST; maze[7][4] = EXIST; maze[7][6] = EXIST; maze[7][7] = EXIST; maze[8][1] = EXIST; } /******************************************************************************* init_start_end_block：初始化代表起点和终点的通道块 *******************************************************************************/ void init_start_end_block(void) { start_block = malloc(sizeof(struct mazeblock)); if(start_block == NULL){ printf("Error, malloc is failed.\n"); exit(EXIT_FAILURE); } start_block->seat.x = 1; start_block->seat.y = 1; start_block->ord = north; start_block->next = NULL; end_block = malloc(sizeof(struct mazeblock)); if(end_block == NULL){ printf("Error, malloc is failed.\n"); exit(EXIT_FAILURE); } end_block->seat.x = 8; end_block->seat.y = 8; } /******************************************************************************* is_next_block_pass：根据当前路径中最后一个通道块的seat与ord判断下一个通道块的坐标 并判断改坐标的通道块是否为"墙" 返回值:FALSE：该方向上的通道块为墙(障碍) TRUE：该方向上的通道块不是墙体 说明：方法中需要修改next_block的值，以确保next_block在需要时 可以存储至路径栈中 *******************************************************************************/ Bool is_next_block_pass(void) { Ordinate target_ord; int next_block_x, next_block_y; Bool is_block_exist; /*标志下一个通道块是否已经存在于路径链表中 TRUE表示已经存在*/ target_ord = curr_block->ord; /*当前路径中最后一个通道块指向下一个的方向*/ next_block = malloc(sizeof(struct mazeblock)); if(next_block == NULL){ printf("Error, malloc is failed.\n"); exit(EXIT_FAILURE); } switch(target_ord){ case north: next_block->seat.x = (curr_block->seat.x) - 1; next_block->seat.y = curr_block->seat.y; break; case east: next_block->seat.x = curr_block->seat.x; next_block->seat.y = (curr_block->seat.y) + 1; break; case south: next_block->seat.x = (curr_block->seat.x) + 1; next_block->seat.y = curr_block->seat.y; break; case west: next_block->seat.x = curr_block->seat.x; next_block->seat.y = (curr_block->seat.y) - 1 ; break; } next_block_x = next_block->seat.x; next_block_y = next_block->seat.y; is_block_exist = find_block(next_block); if(maze[next_block_x][next_block_y] == EXIST || is_block_exist == TRUE){ free(next_block); return FALSE; }else{ return TRUE; } } /******************************************************************************* get_maze_path：求取走出迷宫的路径 *******************************************************************************/ void get_maze_path(void) { /* 思路：首先将起点通道块入栈，然后将栈中栈顶元素标记为curr_block 进入循环中，根据curr_block的ord得到next_block，判断并执行相应操作 */ Bool next_status; init_contents(); /*初始化一个栈*/ push(start_block); /*将起点通道块入栈*/ /*路线求取的总循环退出条件 1.无路线 2.到终点 */ while(start_block->ord != no_road){ curr_block = get_top_value(); if(curr_block->seat.x == 8 && curr_block->seat.y == 8){ break; } if(curr_block->ord == no_road){ pop(); curr_block = get_top_value(); (curr_block->ord)++; continue; } next_status = is_next_block_pass(); if(next_status == TRUE){ next_block->ord = north; push(next_block); continue; }else{ (curr_block->ord)++; } } } /******************************************************************************* print_path：将迷宫通道打印出来 *******************************************************************************/ void print_path(void) { int i, j; for(i = 0; i < 10; i++){ for(j = 0; j < 10; j++){ if(maze[i][j] == EXIST){ printf("#"); }else if(find_block_by_x_and_y_index(i, j) == TRUE){ printf("."); }else{ printf(" "); } } putchar('\n'); } putchar('\n'); }