欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

老鼠走迷宫

程序员文章站 2023-12-24 20:43:39
...

老鼠走迷宫
1)找一组解

#include<stdio.h>
#define r 4
#define c 4

//表示移动的四个方向
int Move[4][2]={
        {0,1},
        {1,0},
        {-1,0},
        {0,-1}
    };

//表示迷宫
int m[r+2][c+2]={
        {1,1,1,1,1,1},
        {1,0,0,1,0,1},
        {1,1,0,1,0,1},
        {1,0,0,1,0,1},
        {1,0,0,0,0,1},
        {1,1,1,1,1,1}
    };
//表示走过的路
int t[r+2][c+2]={0};

int Maze(int x,int y)
{
    //到达终点
    if(x==1 && y==4)
    {
        printf("(%d,%d)-->",x,y);
        return 1;
    }

    //往四个方向走
    for(int i=0;i<4;i++)
    {
        int a=x+Move[i][0];
        int b=y+Move[i][1];
        //如果移动的位置不是墙,且木有走过
        if(m[a][b]!=1 && t[a][b]!=1)
        {
            t[a][b]=1;//把该位置占
            int flag=Maze(a,b);//继续往下走

            //flag用来是区别到达终点,还是不符合往回走
            if(flag)
            {
                printf("(%d,%d)--->",x,y);
                return 1;
            }
        }
    }
    return 0;
}

int main(void)
{   
    t[1][1]=1;
    Maze(1,1);

    return 0;
}

2)所有解

#include<stdio.h>
#define r 4
#define c 4

int Move[4][2]={
        {0,1},
        {1,0},
        {-1,0},
        {0,-1}
    };

int m[r+2][c+2]={
        {1,1,1,1,1,1},
        {1,0,0,1,0,1},
        {1,1,0,0,0,1},
        {1,0,0,1,0,1},
        {1,0,0,0,0,1},
        {1,1,1,1,1,1}
    };

int t[r+2][c+2]={0};
int s[r*c][2];//用栈,存放走过的路径
int top=-1;//栈顶指针
int cnt=0;//统计情况
void show()
{
    printf("%d:\n",++cnt);
    for(int i=0;i<=top;i++)
    {
        printf("(%d,%d)-->",s[i][0],s[i][1]);
    }
    printf("\n");
}

void Maze(int x,int y)
{
    int i,a,b;
    if(x==1 && y==4)
    {
        show();
        return;
    }

    for(i=0;i<4;i++)
    {
        a=x+Move[i][0];
        b=y+Move[i][1];

        if(m[a][b]!=1 && t[a][b]!=1)
        {
            t[a][b]=1;
            s[++top][0]=a;
            s[top][1]=b;
            Maze(a,b);
            t[a][b]=0;
            top--;  
        }
    }
}

int main(void)
{   
    t[1][1]=1;
    s[++top][0]=1;
    s[top][1]=1;

    Maze(1,1);

    return 0;
}

3)去除t

#include<stdio.h>
#define r 4
#define c 4

int Move[4][2]={
        {0,1},
        {1,0},
        {-1,0},
        {0,-1}
    };

int m[r+2][c+2]={
        {2,2,2,2,2,2},
        {2,0,0,2,0,2},
        {2,2,0,0,0,2},
        {2,0,0,2,0,2},
        {2,0,0,0,0,2},
        {2,2,2,2,2,2}
    };

int s[r*c][2];
int top=-1;
int cnt=0;
void show()
{
    printf("%d:\n",++cnt);
    for(int i=0;i<=top;i++)
    {
        printf("(%d,%d)-->",s[i][0],s[i][1]);
    }
    printf("\n");
}

void Maze(int x,int y)
{
    int i,a,b;
    if(x==1 && y==4)
    {
        show();
        return;
    }

    for(i=0;i<4;i++)
    {
        a=x+Move[i][0];
        b=y+Move[i][1];
        //2为墙,1为走过的,0为未走的
        if(m[a][b]!=2 && m[a][b]!=1)
        {
            m[a][b]=1;
            s[++top][0]=a;
            s[top][1]=b;
            Maze(a,b);
            m[a][b]=0;
            top--;  
        }
    }
}

int main(void)
{   
    m[1][1]=1;
    s[++top][0]=1;
    s[top][1]=1;

    Maze(1,1);

    return 0;
}

4)存所有情况,找最优解

#include<stdio.h>
#include<stdlib.h>
#define r 4
#define c 4

int Move[4][2]={
        {0,1},
        {1,0},
        {-1,0},
        {0,-1}
    };

int m[r+2][c+2]={
        {2,2,2,2,2,2},
        {2,0,0,2,0,2},
        {2,2,0,0,0,2},
        {2,0,0,2,0,2},
        {2,0,0,0,0,2},
        {2,2,2,2,2,2}
    };

int s[r*c][2];
int top=-1;
int cnt=0;

typedef struct elem{
    int now[2];
    struct elem *nextstep;
}Step;

typedef struct node{
    int allstep;
    Step *nextstep;
    struct node *next;
}ElemSN;

ElemSN *head=NULL,*tail;
void show()
{
    /*printf("%d:\n",++cnt);
    for(int i=0;i<=top;i++)
    {
        printf("(%d,%d)-->",s[i][0],s[i][1]);
    }
    printf("\n");*/
    int i=0;
    Step *p,*t;
    if(!head)
        head=tail=(ElemSN *)malloc(sizeof(ElemSN));
    else
        tail=tail->next=(ElemSN *)malloc(sizeof(ElemSN));
    tail->next=NULL;
    tail->nextstep=NULL;
    tail->allstep=top+1;//总步逐数

    t=tail->nextstep;
    while(i<=top)
    {
        p=(Step*)malloc(sizeof(Step));
        p->nextstep=NULL;
        (p->now)[0]=s[i][0];
        (p->now)[1]=s[i][1];

        if(!t)
            tail->nextstep=t=p;
        else
            t=t->nextstep=p;
        i++;
    }
}

void Maze(int x,int y)
{
    int i,a,b;
    if(x==1 && y==4)
    {
        show();
        return;
    }

    for(i=0;i<4;i++)
    {
        a=x+Move[i][0];
        b=y+Move[i][1];

        if(m[a][b]!=2 && m[a][b]!=1)
        {
            m[a][b]=1;
            s[++top][0]=a;
            s[top][1]=b;
            Maze(a,b);
            m[a][b]=0;
            top--;  
        }
    }
}


void printLink()
{
    ElemSN *p;
    Step *q;
    int i=0;
    for(p=head;p;p=p->next)
    {
        printf("%d:\n",++i);
        for(q=p->nextstep;q;q=q->nextstep)
            printf("-->(%d,%d)",(q->now)[0],(q->now)[1]);
        printf("\n");
    }
}
int main(void)
{   
    m[1][1]=1;
    s[++top][0]=1;
    s[top][1]=1;

    Maze(1,1);
    printLink();
    return 0;
}
相关标签: c语言

上一篇:

下一篇: