龙空技术网

第四章 递归与回溯 (补全迷宫代码maze.c)

achingz 74

前言:

现时咱们对“c语言迷宫问题实验报告”可能比较重视,同学们都想要学习一些“c语言迷宫问题实验报告”的相关知识。那么小编也在网摘上收集了一些有关“c语言迷宫问题实验报告””的相关知识,希望大家能喜欢,我们一起来学习一下吧!

#include <stdio.h>#include <stdlib.h> /* malloc(),free() */#include <memory.h> /* memory.h */typedef struct Trace{	int row;	int col;}Trace;/* 输出入口到出口的路径paths */void outputPath(int *maze, int rows, int cols, int step, Trace paths[]){	int i, j;	for(i=0; i<step; i++) {		maze[paths[i].row*cols+paths[i].col] = 6;	}	for(i=0; i<rows; i++) {		for(j=0; j<cols; j++) {			printf("%d", maze[i*cols+j]);		}		printf("\n");	}	for(i=0; i<step; i++) {		maze[paths[i].row*cols+paths[i].col] = 0;	}}/* 内部函数:在迷宫maze[rows][cols]中的位置(row,col)寻找到出口的路径 */int findPath_(int *maze, int rows, int cols, int *flag, int row, int col, int step, Trace paths[]){	static int next_row_col[4][2] = {		{-1, 0}, /* 上 */		{1, 0},  /* 下 */		{0, -1}, /* 左 */		{0, 1},  /* 右 */	};	int i, next_row, next_col, index;	static int n=0; /* 统计路径数量 */	if ((row == rows-1) && (col == cols-1)) { /* 到达出口 */		printf("\n[%dth]:\n", ++n);		paths[step].row = row;		paths[step].col = col;		outputPath(maze, rows, cols, step+1, paths);		return 1;	}	/* 迷宫越界判断 */	if (row<0 || col<0 || row>=rows || col>=cols) {		return 0;	}	/* 到此一游 */	flag[row * cols + col] = 1; 	paths[step].row = row;	paths[step].col = col;	/* 探索上下左右4个方向 */	for(i=0; i<4; i++) {		next_row = row + next_row_col[i][0];		next_col = col + next_row_col[i][1];		index = next_row * cols + next_col; /* 试探的位置 */		if ((maze[index] == 0)&&(flag[index] == 0)) { /* 迷宫可走,并且未走过 */			findPath_(maze, rows, cols, flag, next_row, next_col, step+1, paths);		}	}	flag[row * cols + col] = 0; /* 清除痕迹!!! */	return n;}/* 在迷宫maze[rows][cols]中由入口(0,0)寻找到出口的路径 */int findPath(int *maze, int rows, int cols){	int *flag; /* 到此一游的标志数组 */	Trace *paths; /* 入口到出口的路径数组 */	flag = malloc(sizeof(int)*rows*cols); 	paths = malloc(sizeof(Trace)*rows*cols);	memset(flag, 0, sizeof(int)*rows*cols);	return findPath_(maze, rows, cols, flag, 0, 0, 0, paths);}int main(){	int maze[8][10] = {		{0,0,0,1,0,0,0,0,0,0},		{0,1,0,0,1,0,0,1,1,0},		{0,1,1,0,0,1,0,1,0,0},		{0,0,0,1,0,0,0,1,0,1},		{0,1,0,0,0,1,1,1,0,0},		{0,0,1,0,1,0,0,0,1,0},		{1,0,1,0,0,0,1,0,1,0},		{0,0,0,0,1,0,1,0,0,0},	};	findPath(maze[0], 8, 10);	return 0;}

标签: #c语言迷宫问题实验报告 #c语言程序迷宫