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

本程序通过栈的机制（先进后出）来走迷宫。

原理如下：

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,1,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,0},
    {1,0,1,1,0,0,0,0,0,1,0},
    {1,0,1,1,0,1,0,1,0,1,0},
    {1,0,1,1,0,1,0,0,0,0,0}
};

其中 1 为石头，0为通路。以 x=1,y=1为起点.x=10,y=10为终点。
现在先模拟走迷宫

#define GG  程序搜索栈顶的点的上、下、左、右、四个方向是否可以通过，其中某一个方向可以通过。停止搜索其他方向

1. 将（1，1）压入栈中，然后 GG  。找到（2,1）为0 可以走。
2. 将（2,2） 压栈，此时栈中的内容为top ->（2,2）（1,1） ->buttom.此时再次GG  。(3,1)可以走
以此类推..

直到找到终点为止
但是本次使用的是深度优先搜索算法，得到的并不是最佳的路径，仅仅是一条可靠的路径而已。

本次走迷宫使用深度优先搜索算法的目的是找出所有的走迷宫的方法、路径。这个功能后续优化

#include <stdio.h>

#define SIZE 10

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

Point Stack[100];
int buttom;
int top;

int visit[SIZE+1][SIZE+1];
int Show_buff[11][11];

int buff[SIZE+1][SIZE+1] = {
    {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,0},
    {1,0,1,1,0,0,0,0,0,1,0},
    {1,0,1,1,0,1,0,1,0,1,0},
    {1,0,1,1,0,1,0,0,0,0,0}
};

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

int Stack_Is_Empty()
{
    if(buttom == top)
        return 1;

    return 0;
}

void Add_Stack_Top(Point p)
{
    Stack[top] = p;

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

Point Del_Stack_Top(void)
{
    Point p;

    top--;
    if(top<0){
        top = 99;
    }

    p = Stack[top];
    Stack[top].x = 0;
    Stack[top].y = 0;

    return p;
}

Point Get_Stack_Top(void)
{
    return  Stack[top-1];
}

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) || (visit[x][y] == 2))
        return 1;

    return 0;
}

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


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

void Disply_Stack(void)
{
    Point p;
    int w_head,w_tail;
    w_head = buttom;
    w_tail = top;

    printf("\n---------------------------------------------\n");
    while(w_head != w_tail){

        p = Stack[w_head];
        w_head ++;

        printf("( %d,%d )",p.x,p.y);
        if(w_head>99)
            w_head=0;

    }
    printf("\n---------------------------------------------\n");
}

void Disply_Game(void)
{
    Point p;
    int i,j,w_head,w_tail;
    w_head = buttom;
    w_tail = top;

    for(i=0;i<11;i++){
        for(j=0;j<11;j++)
        {
            Show_buff[i][j] = 0;
        }
    }

    while(w_head != w_tail){

        p = Stack[w_head];
        w_head ++;
        Show_buff[p.x][p.y] = 1;
        if(w_head>99)
            w_head=0;

    }
    printf("\n------------------------------------------------\n");
    for(i=1;i<11;i++){
        printf("  ");
        for(j=1;j<11;j++)
        {
            if(Show_buff[i][j] == 1){
                printf("0 ");
            }else{
                printf("  ");
            }
        }
        printf(" \n");
    }
    printf("------------------------------------------------\n");
}

int DFS(Point start, Point end)
{
    int i,count=0;
    Point temp,Add_temp;
    Set_Visit(start);
    Add_Stack_Top(start);

    if(buff[end.x][end.y] == 1){
        printf("end (%d,%d) is 1 can't goto",end.x, end.y);
        return 0;
    }

    while(!Stack_Is_Empty()){
        Disply_Stack();
        temp = Get_Stack_Top();

        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] == end.x) && (temp.y+direction[i][1] == end.y)){

                printf("\nI find it (%d,%d) Step = %d \n",end.x, end.y, 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_Top(Add_temp);
                Set_Visit(Add_temp);
                break;
            }
            if(i==3){
                temp = Del_Stack_Top();
                printf("delete post = %d %d",temp.x,temp.y);
                Set_Visit_Die(temp);
            }
        }
    }

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

int main(void){

    Point p_start,p_end;
    p_start.x = 1;
    p_start.y = 1;
    p_start.Step = 1;

    p_end.x = 10;
    p_end.y = 10;

    Init_Visit();
    Init_Stack();

    if(DFS(p_start, p_end))
        Disply_Game();

    return 0;
}