maze1..txt

来自「用C编写的迷宫最短路径。另有一用VC编写的」· 文本 代码 · 共 249 行

#include <stdlib.h>
#include <stdio.h>


#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];


/* --------------------------------------------------*/
#define true 1
#define false 0

typedef struct {
	int xpos;
	int ypos;
} PosType;


typedef struct DQNode {
	PosType seat;
	struct DQNode *next;
	struct DQNode *pre;
} DQNode, *DQueuePtr;

typedef struct {
	DQueuePtr front;
	DQueuePtr rear;
} DLinkQueue;


/* --------------------------------------------------*/
typedef struct {
	PosType storage[1000];
	int top;
} Stack;

int IsEmpty(Stack *stack)
{
	return stack->top == 0;
}

void Push(Stack *stack, PosType seat)
{
	int top = stack->top;
	stack->storage[top].xpos = seat.xpos;
	stack->storage[top].ypos = seat.ypos;

	stack->top++;
}

PosType Pop(Stack *stack)
{
	PosType result;
	if (IsEmpty(stack)) { 
		result.xpos = -1;
		result.ypos = -1;
	}
	else {
		int top = stack->top;
		result.xpos = stack->storage[top-1].xpos;
		result.ypos = stack->storage[top-1].ypos;
		stack->top--;
	}

	return result;
}


void InitStack(Stack *stack)
{
	stack->top = 0;
}

/* --------------------------------------------------*/

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;
}

void print_maze()
{
	int i, j;
	printf("--------- the maze ----------\n");
	for (i = 0; i < M; i++) {
		for (j = 0; j < N; j++) {
			printf("%d   ", maze[i][j]);
		}
		printf("\n");
	}
	printf("-----------------------------\n");
}

int main()
{
	Stack stack;
	PosType seat;

	print_maze();
	
	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;
}