实验题目：迷宫问题

实验题目：迷宫问题
实验目的：
1．熟悉栈用法；
2．掌握回朔法及试探法程序设计技能。

#include <stdio.h>
#define M 8//M为迷宫的行数
#define N 8//N为迷宫的列数
typedef struct Mz
{
	int i;
	int j;
	int pre;
}Mz, Box;
typedef struct queue
{
	int front, rear;//队列的头指针和尾指针
	Box data[100];
}queue;
int maze[M + 2][N + 2] = {
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1} };
void output(queue q, int front)
{
	int temp, k = 0;
	while (front != 0)
	{
		temp = front;
		front = q.data[front].pre;
		q.data[temp].pre = -1;
	}
	k = 0;
	while (k < 100)
	{
		if (q.data[k].pre == -1)
		{
			printf("(%d,%d) ", q.data[k].i, q.data[k].j);
		}
		k++;
	}
	printf("\n");
}
void Path(int x, int y)
{
	queue q;
	int tempx, tempy, direction;
	tempx = tempy = 0;
	q.front = q.rear = -1;
	q.rear++;
	q.data[q.rear].i = x;
	q.data[q.rear].j = y;
	q.data[q.rear].pre = -1;
	maze[x][y] = -1;
	while (q.front != q.rear)
	{
		q.front++;
		tempx = q.data[q.front].i;
		tempy = q.data[q.front].j;
		if (tempx == M && tempy == N)
		{
			printf("路线为：\n");
			output(q, q.front);
			return;
		}
		for (direction = 0; direction < 4; direction++)
		{
			switch (direction)
			{
			case 0:
				tempx = q.data[q.front].i;
				tempy = q.data[q.front].j - 1;
				break;
			case 1:
				tempx = q.data[q.front].i + 1;
				tempy = q.data[q.front].j;
				break;
			case 2:
				tempx = q.data[q.front].i;
				tempy = q.data[q.front].j + 1;
				break;
			case 3:
				tempx = q.data[q.front].i - 1;
				tempy = q.data[q.front].j;
				break;
			}
			if (maze[tempx][tempy] == 0)
			{
				q.rear++;
				q.data[q.rear].i = tempx;
				q.data[q.rear].j = tempy;
				q.data[q.rear].pre = q.front;
				maze[tempx][tempy] = -1;
			}

		}
	}
	printf("无法找到一条可以走到终点的路线！\n");
	return;
}
int main()
{
	int i, j;

	for (i = 0; i < M + 2; i++)
	{
		for (j = 0; j < N + 2; j++)
		{
			printf("%d ", maze[i][j]);
		}
		printf("\n");
	}
	Path(1, 1);
}

这是我大二的实验，希望对大家有帮助，代码我是在vs写的，运行都是对的，要是不对就把scanf_s
改回scanf