首页
论坛
专栏
课程

[旧帖] [原创]吃豆子问题的解法-《加密与解密》 0.00元

2011-7-8 14:50 1248

[旧帖] [原创]吃豆子问题的解法-《加密与解密》 0.00元

2011-7-8 14:50
1248
本人新手,最近在读《加密与解密》,看到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;
}



参考了网上一个迷宫求解:http://hi.baidu.com/%C1%CB%C8%BB%D2%B2/blog/item/24661808b80df72f6b60fb91.html

2020安全开发者峰会(2020 SDC)议题征集 中国.北京 7月!

上传的附件:
  • 1.JPG (13.21kb,61次下载)
最新回复 (3)
xulay 1 2011-7-8 15:20
2
0
点出程序的要点才能给人以启示。
hdchild 2011-7-8 15:40
3
0
恩,我修改了下
zapline 2011-7-8 16:24
4
0
简单的ACM题目 没意思
游客
登录 | 注册 方可回帖
返回