老鼠走迷宫
程序员文章站
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;
}