IT牛人博客聚合

今天下午花了很久的时候做了一个走迷宫的题目。其实这个题目以前上数据结构课的时候都已经写过了，但是再写却又花了很多时间，虽然代码结构和以前写的不一样，但是这却不是最花时间的地方。大部分的时间都花在Debug一些很低级的bug上面，是我状态不好呢，还是写程序实在太烂了呢 Orz。

近来烦心事很多，确实很影响状态。不过就这次的练习来说，还是可以挖出自己很多不好的编程习惯的。总有来说，我要注意：

1. 训练对问题的抽象能力。看到一个问题时，要能够选择出合适的数据结构去把这个问题转化成计算机可以处理的形式。
2. 加强对数据结构的记忆，写逻辑已经先写出数据结构的定义及其上的操作，以后可以方便直接用。
3. 先把问题分析透，用纸笔或者伪代码先把流程写清楚再编码，急于求成只会引入更多的bug。

下面是代码，可以找出所有的路径，很简单哦。

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

#define Z 0
#define E 1
#define S 2
#define W 3
#define N 4
#define F 5

#define MAX_STACK_SIZE 1000

/* 0 means clear, 1 means blocked */
#define X 5
#define Y 4
int maze[X][Y] = {
	{0, 0, 1, 0},
	{1, 0, 0, 1},
	{1, 0, 1, 1},
	{0, 0, 0, 1},
	{1, 0, 0, 0}
};

typedef struct {
	int x, y;
	int direction;
} coord;

int   top = -1;
coord stack[MAX_STACK_SIZE];

#define PUSH(c)						\
	do {						\
		if (++top > MAX_STACK_SIZE) {		\
			printf("Stack overflowed\n");	\
			exit(-1);			\
		}					\
		stack[top] = c;				\
	} while (0)

#define POP(c)						\
	do {						\
		if (top == -1) {			\
			printf("Stack underflowed\n");	\
			exit(-1);			\
		}					\
		c = stack[--top];			\
	} while (0)

#define EMPTY() (top == -1)

#define EQUAL(c1, c2) (c1.x==c2.x && c1.y==c2.y)

#define EXISTS(c) exists(c)

#define IS_VALID_MOVE(c) \
	( !maze[c.x][c.y] && c.x >= 0 && c.x < X && c.y >= 0 && c.y < Y )

int exists(coord c)
{
	int i, res = 0;
	for (i = 0; i <= top; ++i) {
		if (EQUAL(stack[i], c)) {
			res = 1;
			break;
		}
	}
	return res;
}

int main()
{
	coord fini_coord = { 4, 3, 0} , start_coord = { 0, 0, 0 };
	int found = 0;
	coord t, t1;
	int i;

	PUSH(start_coord);
	while (!EMPTY()) {
		t = stack[top];
		t1 = t;
		if ((EQUAL(t, fini_coord))) {
			found++;
			printf("Path %d:\n", found);
			for (i = 0; i <= top; i++)
				printf("(%d, %d)\n", stack[i].x, stack[i].y);
			printf("\n\n");
			POP(t1);
			continue;
		}

		switch (t.direction) {
		case Z:
			t.direction = E;
			stack[top] = t;
			t1 = t;
			t1.y += 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);

			break;

		case E:
			t.direction = S;
			stack[top] = t;
			t1 = t;
			t1.x += 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);
			break;

		case S:
			t.direction = W;
			stack[top] = t;
			t1 = t;
			t1.y -= 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);
			break;
		case W:
			t.direction = N;
			stack[top] = t;
			t1 = t;
			t1.x -= 1;
			t1.direction = 0;
			if (IS_VALID_MOVE(t1) && !EQUAL(stack[top-1], t1) && !EXISTS(t1))
				PUSH(t1);
			break;
		case N:
			t.direction = 5;
			stack[top] = t;
			break;
		case F:
			POP(t1);
			break;
		default:
			printf("BUG: unknown direction\n");
			exit(-1);
		}
	}

	if (!found)
		printf("No path found\n");

	return 0;
}

© 2011,liuw. All rights reserved.