【初学算法】之深度优先搜索算法 实现走迷宫计算出步数

代码如下：

#include <stdio.h>

typedef struct point{
    int x;
    int y;
    int Step;
}Point;

Point Stack[100];
int head;
int tail;


void Init_Stack(void)
{
    int i;
    for(i=0;i<100;i++){
        Stack[i].x = 0;
        Stack[i].y = 0;
    }
    head = 0;
    tail = 0;
}

int Stack_Is_Empty()
{
    if(head == tail)
        return 1;

    return 0;
}

void Add_Stack_Head(Point p)
{
    Stack[tail] = p;

    tail++;
    if(tail>99){
        tail = 0;
    }
}

Point Del_Stack_Head(void)
{
    Point p;
    p = Stack[head];
    Stack[head].x = 0;
    Stack[head].y = 0;
    head++;
    if(head>99){
        head = 0;
    }
    return p;
}

int buff[11][11] = {
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,0,1,1,0,1,0,1,1,0,0},
    {1,0,1,1,0,1,0,1,0,0,0},
    {1,0,0,0,0,0,0,0,0,1,0},
    {1,0,1,1,0,1,0,1,1,0,0},
    {1,0,1,1,0,1,0,0,0,0,1},
    {1,0,1,0,0,1,0,1,1,0,1},
    {1,0,0,0,0,0,0,0,1,0,1},
    {1,0,1,1,0,0,0,0,0,0,0},
    {1,0,1,1,0,1,0,1,0,0,0},
    {1,0,1,1,0,1,0,0,0,0,0}
};

int visit[11][11];


void Init_Visit(void)
{
    int i,j;
    for(i=0;i<11;i++){
        for(j=0;j<1;j++){
            visit[i][j] = 0;
        }
    }
}

int Is_Visit(int x, int y){

    if(visit[x][y] == 1)
        return 1;

    return 0;
}

void Set_Visit(Point p)
{
    visit[p.x][p.y] = 1;
}


int direction[4][2] = {
    {-1,0},{1,0},{0,-1},{0,1} //up down left right
};


int DFS(Point p)
{
    int i;
    Point temp,Add_temp;
    Set_Visit(p);
    Add_Stack_Head(p);

    while(!Stack_Is_Empty()){

        temp = Del_Stack_Head();

        for(i=0;i<4;i++){

            if((temp.x+direction[i][0] > 10) || (temp.x+ direction[i][0] <1) || (temp.y + direction[i][1] > 10) || (temp.y + direction[i][1] < 1)){
                continue;
            }

            if((temp.x+direction[i][0] == 10) && (temp.y+direction[i][1] == 10)){
                printf("I find it %d",temp.Step);
                return 1;
            }

            if((!Is_Visit(temp.x+direction[i][0],temp.y +direction[i][1])) && buff[temp.x +direction[i][0]][temp.y + direction[i][1]] == 0){
                Add_temp.x = temp.x+direction[i][0];
                Add_temp.y = temp.y+direction[i][1];
                Add_temp.Step = temp.Step + 1;
                Add_Stack_Head(Add_temp);
                Set_Visit(Add_temp);
            }
        }
    }

    printf("\n end \n");
    return 0;
}

int main(void){

    Point p;
    p.x = 1;
    p.y = 1;
    p.Step = 1;

    Init_Visit();
    Init_Stack();

    DFS(p);



    return 0;
}