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

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课