本人新手，最近在读《加密与解密》，看到5.5.2节中提到了吃豆子(peckme)的问题，根据图形，我们肉眼是很容易看出如何走到X
，但是总感觉缺点什么
，于是参考迷宫的求解问题，写了一个大概的求解程序。本人新手，望轻拍
（由于VC中中文注释有乱码我问题，只能用我憋足的英文加点注释了）
迷宫算法的思路：根据当前的位置，按上、右、下、左四个方向进行试探，如果其中一条路可以走通，则把可以走通的路记录下来(压栈)；
如果四条路都是走不通，那么当前节点是无法达到目的地的，将其删除(出栈)。其实是一种穷举的方式，下面举个例子进行说明
图中阴影部分表示是墙，即不可通过。现假设现在我站在A点，要到B点。根据算法首先试探A的上面，是空的，然后试探A的右边是C，OK，走到C（C进栈），C按照规则发现没有方向可以行得通，退回来，返回到A（C出栈），A已经探测过C了，下面探测D，OK，走到D（D进栈），D继续进行探测，探测到E，E探测到F，F探测到B，OK，找到了
。
代码:
/****************************************
file:
pec.c
purpose:
find the way to taget
author:
hdchild
date:
2011-07-08
***************************************/
#include <stdio.h>
/**<p>define the width and lenth of maz with MACRO</p>**/
#define MAZ_LENGTH (16)
#define MAZ_WIDTH (sizeof(pec)/MAZ_LENGTH)
/**<p>define the direction of the current node can move to</p>*/
#define DIRECT_UP 1
#define DIRECT_RIGHT 2
#define DIRECT_DOWN 3
#define DIRECT_LEFT 4
/**<p>define the state of every node in maz, 0 means cann't go, 1 means can go and 2 means got it</p>*/
#define MAZ_BLOCK 0
#define MAZ_PASS 1
#define MAZ_TARGET 2
/**define the stack node*/
typedef struct stack_node_struct stack_node_t;
struct stack_node_struct
{
int i; // the (i)th line , begin with zero
int j; // the j th column, begin with zero;
int direct; // the direction of the node, see the defination of MACRO DIRECT_XXX
};
/**here is the orginal maz**/
char pec[] = "C*......*...****.*.****...*....*.*..**********\
.*..*....*...*...**.****.*.*..\
.****.*....*.*******..*.***..*.\
....*.*..***.**.***.*...****.\
...*X..*****************";
/**<p>the state array of the maz</p>*/
char maz[MAZ_WIDTH][MAZ_LENGTH]= {MAZ_BLOCK};
/**<p>the fallow is struct of my stack, include interface : pop, push, top etc</p>*/
stack_node_t stack[MAZ_WIDTH * MAZ_LENGTH];
int stack_top = 0;
stack_node_t*
pop()
{
stack_top--;
return &stack[stack_top];
}
stack_node_t*
top()
{
return &stack[stack_top-1];
}
int
is_empty(
)
{
return stack_top == 0;
}
void
push(
int i,
int j
)
{
stack[stack_top].i = i;
stack[stack_top].j = j;
stack[stack_top].direct = 0;
stack_top++;
}
/**<p>format the maz from the orginal pec</p>*/
void
format_maz()
{
int i, j;
int pec_pos;
char apec;
for (i = 0; i < MAZ_WIDTH; i++)
{
for (j = 0; j < MAZ_LENGTH; j++)
{
/**calc the position in pec*/
pec_pos = MAZ_LENGTH * i + j;
apec = pec[pec_pos];
if (apec == '.' || apec == 'C')
{
maz[i][j] = MAZ_PASS;
}
else if (apec == 'X')
{
maz[i][j] = MAZ_TARGET;
}
else
maz[i][j] = MAZ_BLOCK;
}
}
/**<p>just for test</p>*/
for (i = 0; i < MAZ_WIDTH; i++)
{
for (j = 0; j < MAZ_LENGTH; j++)
{
printf("%c ", (maz[i][j] != MAZ_BLOCK) ? (maz[i][j] == MAZ_TARGET? 'X' : '.') : '*');
}
printf("\n");
}
}
int
maz_can_go(
int i,
int j
)
{
if (i < 0 || i >= MAZ_WIDTH)
return 0;
if (j < 0 || j >= MAZ_LENGTH)
return 0;
return maz[i][j];
}
/**<p>find a way we can go to target</p>*/
void
find_wayout()
{
stack_node_t* cur_node;
int i, j, direct;
int found;
while (stack_top > 0)
{
cur_node = top();
i = cur_node->i;
j = cur_node->j;
/**here we got the target, return */
if (maz[i][j] == MAZ_TARGET)
return;
direct = cur_node->direct;
found = 0;
/**traverse every direction */
while (direct < DIRECT_LEFT && !found)
{
direct++;
switch (direct)
{
case DIRECT_UP:
i = cur_node->i - 1;
j = cur_node->j;
break;
case DIRECT_RIGHT:
i = cur_node->i;
j = cur_node->j + 1;
break;
case DIRECT_DOWN:
i = cur_node->i + 1;
j = cur_node->j;
break;
case DIRECT_LEFT:
i = cur_node->i;
j = cur_node->j - 1;
break;
default:
break;
}
if (maz_can_go(i, j))
found = 1;
}
/**if found a way can go on, the push the current node
and make it state to BLOCK, to avoid circle*/
if (found)
{
maz[cur_node->i][cur_node->j] = MAZ_BLOCK;
cur_node->direct = direct;
push(i, j);
}
else //else there is no way to go ,pop the current node and make it state to PASS
{
maz[cur_node->i][cur_node->j] = MAZ_PASS;
pop();
}
}
}
/**<p>print the way we find </p>*/
void
print_way(
)
{
int i;
char direct[][10] = {"^", "->", "!", "<-"};
if (stack_top == 0)
{
printf("No Way!\n");
}
else
{
printf("Note : \n\t\t '^' means move up \n\t\t '->' means move right \n\t\t '!' means move down \n\t\t '<-' means move left\n");
for (i = 0; i < stack_top - 1; i++)
{
printf("The %d step : %s\n", i, direct[stack[i].direct - 1]);
}
}
}
int
main(void)
{
format_maz();
/**push the start node*/
push(0, 0);
find_wayout();
print_way();
return 0;
}