maze.c

用VC编写的迷宫最短路径求解。

// Maze.cpp : Defines the entry point for the console application.
//
#include <stdlib.h>
#include <stdio.h>
#include "DataTypes.h"
#include "Stack.c"
#define M 6
#define N 8
int maze[M][N] = {
	{0, 0, 1, 1, 0, 0, 0, 1},
	{1, 0, 1, 0, 1, 1, 1, 0},
	{0, 1, 1, 1, 0, 1, 1, 0},
	{0, 1, 1, 0, 1, 1, 0, 1},
	{0, 0, 1, 0, 1, 0, 1, 1},
	{1, 1, 0, 1, 1, 0, 0, 0}
};
int visited[M][N];

Stack S; // define a stack


PosType NextPos(PosType curpos, int v)
{
	int dx[] = {1, 1, 0, -1, -1, -1,  0,  1};
	int dy[] = {0, 1, 1,  1,  0, -1, -1, -1};

	PosType nextpos;
	nextpos.xpos = curpos.xpos + dx[v];
	nextpos.ypos = curpos.ypos + dy[v];

	return nextpos;
}

int Pass(PosType pos) 
{
	int x = pos.xpos;
	int y = pos.ypos;

	if (x < 0 || x >= M || y < 0 || y >= N) {
		return false;
	}

	if (maze[x][y] == 0 && !visited[x][y]) {
		return true;
	}
	else return false;
}

void InitQueue(DLinkQueue *Q)
{
	Q->front = NULL;
	Q->rear = NULL;
}

void EnQueue(DLinkQueue *Q, PosType e)
{
		DQueuePtr p = (DQueuePtr)malloc(sizeof(DQNode));
		p->seat.xpos = e.xpos;
		p->seat.ypos = e.ypos;
		p->next = NULL;

		if (!Q->rear) {
			p->pre = NULL;
			Q->rear = p; Q->front = p;
		}
		else {
			p->pre = Q->front;
			Q->rear->next = p; Q->rear = p;
		}
}

void GetHead(DLinkQueue Q, PosType *e)
{
	e->xpos = Q.front->seat.xpos;
	e->ypos = Q.front->seat.ypos;
}

void DeQueue(DLinkQueue *Q)
{
	Q->front = Q->front->next;
}

int QueueEmpty(DLinkQueue Q)
{
	return (Q.front == NULL);
}

void printQ(DLinkQueue Q) {
	DQueuePtr p = Q.front;

	printf("=== current queue ====\n"); 
	while (p) {
		printf("x = %d, y = %d\n", p->seat.xpos, p->seat.ypos);
		p = p->next;
	}
	printf("\n\n");
}

int ShortestPath(Stack *S)
{
	int i, j, v, found;
	PosType e;
	DLinkQueue Q;
	DQueuePtr dqPtr;

	InitQueue(&Q);
	for (i = 0; i < M; i++) 
		for (j = 0; j < N; j++) 
			visited[i][j] = false;

	if (maze[0][0] != 0) return false;

	e.xpos = 0; e.ypos = 0; 
	EnQueue(&Q, e);
	visited[0][0] = 1;
	found = false;

	while (!found && !QueueEmpty(Q)) {
		PosType curpos, npos;
		GetHead(Q, &curpos);
		for (v = 0; v < 8 && !found; v++) {
			npos = NextPos(curpos, v);

			if (Pass(npos)) {
				EnQueue(&Q, npos);
				visited[npos.xpos][npos.ypos] = true;
				//printQ(Q); 
			}

			if (npos.xpos == M - 1 && npos.ypos == N -1) {
				found = true;
				break;
			}
		} // for
		DeQueue(&Q);

	}//while

	if (found) {
		InitStack(S);
		dqPtr = Q.rear;
		while (dqPtr) {
			Push(S, dqPtr->seat);
			dqPtr = dqPtr->pre;
		} // while

		return true;
	} // if 
	else return false;
}

int main(int argc, char* argv[])
{
	Stack stack;
	PosType seat;
	if (ShortestPath(&stack)) {;
		printf("The path is ...\n");
		while (!IsEmpty(&stack)) {
			seat = Pop(&stack);
			printf("x = %d, y = %d\n", seat.xpos, seat.ypos);
		}
	}
	else printf("No path is found\n");

	return 0;
}