算法设计迷宫
A. 用数据结构解迷宫
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#define N 20/*迷宫的大小，可改变*/
int oldmap[N][N];/*递归用的数组,用全局变量节约时间*/
int yes=0;/*yes是判断是否找到路的标志,1找到，0没找到*/
int way[100][2],wayn=0;/*way数组是显示路线用的,wayn是统计走了几个格子*/
void Init(void);/*图形初始化*/
void Close(void);/*图形关闭*/
void DrawPeople(int *x,int *y,int n);/*画人工探索物图*/
void PeopleFind(int (*x)[N]);/*人工探索*/
void WayCopy(int (*x)[N],int (*y)[N]);/*为了8个方向的递归，把旧迷宫图拷贝给新数组*/
int FindWay(int (*x)[N],int i,int j);/*自动探索函数*/
void MapRand(int (*x)[N]);/*随机生成迷宫函数*/
void PrMap(int (*x)[N]);/*输出迷宫图函数*/
void Result(void);/*输出结果处理*/
void Find(void);/*成功处理*/
void NotFind(void);/*失败处理*/
void main(void)/*主函数*/
{
int map[N][N]; /*迷宫数组*/
char ch;
clrscr();
printf("\n Please select hand(1) else auto\n");/*选择探索方式*/
scanf("%c",&ch);
Init(); /*初始化*/
MapRand(map);/*生成迷宫*/
PrMap(map);/*显示迷宫图*/
if(ch=='1')
PeopleFind(map);/*人工探索*/
else
FindWay(map,1,1);/*系统自动从下标1,1的地方开始探索*/
Result();/*输出结果*/
Close();
}
void Init(void)/*图形初始化*/
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\tc");
}
void DrawPeople(int *x,int *y,int n)/*画人工控制图*/
{/*如果将以下两句注释掉，则显示人工走过的路径，*/
setfillstyle(SOLID_FILL,WHITE); /*设置白色实体填充样式*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
/*恢复原通路*/
switch(n)/*判断x,y的变化，8个方向的变化*/
{
case 1: (*x)--;break; /*上*/
case 2: (*x)--;(*y)++;break ;/*右上*/
case 3: (*y)++;break; /*右*/
case 4: (*x)++;(*y)++;break; /*右下*/
case 5: (*x)++;break; /*下*/
case 6: (*x)++;(*y)--;break; /*左下*/
case 7: (*y)--;break; /*左*/
case 8: (*x)--;(*y)--;break; /*左上*/
}
setfillstyle(SOLID_FILL,RED);/*新位置显示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
}
void PeopleFind(int (*map)[N])/*人工手动查找*/
{
int x,y;
char c=0;/*接收按键的变量*/
x=y=1;/*人工查找的初始位置*/
setcolor(11);
line(500,200,550,200);
outtextxy(570,197,"d");
line(500,200,450,200);
outtextxy(430,197,"a");
line(500,200,500,150);
outtextxy(497,130,"w");
line(500,200,500,250);
outtextxy(497,270,"x");
line(500,200,450,150);
outtextxy(445,130,"q");
line(500,200,550,150);
outtextxy(550,130,"e");
line(500,200,450,250);
outtextxy(445,270,"z");
line(500,200,550,250);
outtextxy(550,270,"c");/*以上是画8个方向的控制介绍*/
setcolor(YELLOW);
outtextxy(420,290,"Press 'Enter' to end");/*压回车键结束*/
setfillstyle(SOLID_FILL,RED);
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置显示*/
while(c!=13)/*如果按下的不是回车键*/
{
c=getch();/*接收字符后开始各个方向的探索*/
if(c=='w'&&map[x-1][y]!=1)
DrawPeople(&x,&y,1);/*上*/
else
if(c=='e'&&map[x-1][y+1]!=1)
DrawPeople(&x,&y,2);/*右上*/
else
if(c=='d'&&map[x][y+1]!=1)
DrawPeople(&x,&y,3);/*右*/
else
if(c=='c'&&map[x+1][y+1]!=1)
DrawPeople(&x,&y,4);/*右下*/
else
if(c=='x'&&map[x+1][y]!=1)
DrawPeople(&x,&y,5);/*下*/
else
if(c=='z'&&map[x+1][y-1]!=1)
DrawPeople(&x,&y,6); /*左下*/
else
if(c=='a'&&map[x][y-1]!=1)
DrawPeople(&x,&y,7); /*左*/
else if(c=='q'&&map[x-1][y-1]!=1)
DrawPeople(&x,&y,8); /*左上*/
}
setfillstyle(SOLID_FILL,WHITE); /*消去红色探索物，恢复原迷宫图*/
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);
if(x==N-2&&y==N-2)/*人工控制找成功的话*/
yes=1; /*如果成功标志为1*/
}
void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷贝迷宫数组 */
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
oldmap[i][j]=map[i][j];
}
int FindWay(int (*map)[N],int i,int j)/*递归找路*/
{
if(i==N-2&&j==N-2)/*走到出口*/
{
yes=1;/*标志为1,表示成功*/
return;
}
map[i][j]=1;/*走过的地方变为1*/
WayCopy(oldmap,map); /*拷贝迷宫图*/
if(oldmap[i+1][j+1]==0&&!yes)/*判断右下方是否可走*/
{
FindWay(oldmap,i+1,j+1);
if(yes)/*如果到达出口了，再把值赋给显示路线的way数组,也正是这个原因,所以具体路线是从最后开始保存*/
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j]==0&&!yes)/*判断下方是否可以走,如果标志yes已经是1也不用找下去了*/
{
FindWay(oldmap,i+1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j+1]==0&&!yes)/*判断右方是否可以走*/
{
FindWay(oldmap,i,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j]==0&&!yes)/*判断上方是否可以走*/
{
FindWay(oldmap,i-1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j+1]==0&&!yes)/*判断右上方是否可以走*/
{
FindWay(oldmap,i-1,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j-1]==0&&!yes)/*判断左下方是否可以走*/
{
FindWay(oldmap,i+1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j-1]==0&&!yes)/*判断左方是否可以走*/
{
FindWay(oldmap,i,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j-1]==0&&!yes)/*判断左上方是否可以走*/
{
FindWay(oldmap,i-1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
return;
}
void MapRand(int (*map)[N])/*开始的随机迷宫图*/
{
int i,j;
cleardevice();/*清屏*/
randomize(); /*随机数发生器*/
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈为墙壁*/
map[i][j]=1;
else
if(i==1&&j==1||i==N-2&&j==N-2)/*出发点与终点表示为可走的*/
map[i][j]=0;
else
map[i][j]=random(2);/*其它的随机生成0或1*/
}
}
}
void PrMap(int (*map)[N])/*输出迷宫图*/
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(map[i][j]==0)
{
setfillstyle(SOLID_FILL,WHITE);/*白色为可走的路*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
else
{
setfillstyle(SOLID_FILL,BLUE);/*蓝色为墙壁*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
}
void Find(void)/*找到通路*/
{
int i;
setfillstyle(SOLID_FILL,RED);/*红色输出走的具体路线*/
wayn--;
for(i=wayn;i>=0;i--)
{
bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+
way[i][1]*15+6,50+way[i][0]*15+6);
sleep(1);/*控制显示时间*/
}
bar(100+(N-2)*15-6,50+(N-2)*15-6,100+
(N-2)*15+6,50+(N-2)*15+6); /*在目标点标红色*/
setcolor(GREEN);
settextstyle(0,0,2);/*设置字体大小*/
outtextxy(130,400,"Find a way!");
}
void NotFind(void)/*没找到通路*/
{
setcolor(GREEN);
settextstyle(0,0,2);/*设置字体大小*/
outtextxy(130,400,"Not find a way!");
}
void Result(void)/*结果处理*/
{
if(yes)/*如果找到*/
Find();
else/*没找到路*/
NotFind();
getch();
}
void Close(void)/*图形关闭*/
{
closegraph();
}
另外一个，是数据结构的：
#include<stdio.h>
#define NUM 10/* 定义物品总数*/
#define CONTENT 10 /*定义包的容量*/
void knapsack(int v[NUM],int w[NUM],int c,int m[NUM ][CONTENT])
{
int n=NUM-1;
int i,j;
int jMax;
if((w[n]-1)< c)
jMax = w[n]-1;
else
jMax = c;
/* 初始化m[n][j] */
for(j = 0; j <= jMax; j++)
m[n][j] = 0;
for(j = jMax +1; j <= c; j++)
m[n][j] = v[n];
/*使用非递归的算法来求解m[i][j] */
for(i = n-1; i > 0; i--)
{
if((w[i]-1)< c)
jMax = w[i]-1;
else
jMax = c;
for(j = 0; j <= jMax; j++)
m[i][j] = m[i+1][j] ;
for(j = jMax +1; j <= c; j++)
{
if(m[i+1][j] >= (m[i+1][j-w[i]]+v[i]))
m[i][j] = m[i+1][j] ;
else
m[i][j] = m[i+1][j-w[i]]+v[i];
}
}
if(c>w[0])
{
if(m[1][c] >= (m[1][c-w[0]]+v[0]))
m[0][c]= m[1][c];
else
m[0][c]= m[1][c-w[0]]+v[0];
}
else
m[0][c]= m[1][c];
}
/*寻找最优解*/
void traceback(int flag[NUM],int w[NUM],int m[NUM][CONTENT])
{
int n = NUM -1;
int i;
int c = CONTENT;
for(i = 0; i < n; i++)
{
if(m[i][c] == m[i+1][c])
flag[i] = 0;
else
{
flag[i] = 1;
c-=w[i];
}
}
if(m[n][c] >0)
flag[n] = 1;
else
flag[n] = 0;
}
/* 打印最优解*/
void printResult(int flag[NUM],int w[NUM],int v[NUM],int m[NUM][CONTENT])
{
int i;
printf("the knapsack should contain:\n");
printf(" num weight value \n");
for(i = 0;i < NUM; i++)
{
if(flag[i] == 1)
printf(" %d %d %d\n",i,w[i],v[i]);
}
printf("the max value in the knapsack is: %d\n",m[0][CONTENT]);
}
int main()
{
int value[NUM]={5,2,3,4,3,6,5,7,8,2};
int weight[NUM]={2,1,3,2,4,3,5,6,2,2};
int c = CONTENT;
int maxvalue[NUM][CONTENT];
int flag[NUM]={0,0,0,0,0,0,0,0,0,0};
clrscr();
printf("****************************************\n");
printf("* this program will solve *\n");
printf("* the problem of 0-1knapsack *\n");
printf("****************************************\n");
/*计算最优值*/
knapsack(value,weight,c,maxvalue);
/*构造最优解*/
traceback(flag,weight,maxvalue);
/*打印程序的结果*/
printResult(flag,weight,value,maxvalue);
getch();
return 0;
}
B. 试设计迷宫求解算法:迷宫是一个m行n列的0-1矩阵,其中0表示无障碍,1表示有障碍
假设8个方位被简单定义为 char a[8];
int path(point *location)
{
if(“location不为出口”&&“location.a[0]未涉足过”)
path(location->a[0]);
else if(“location不为出口”&&“location.a[1]未涉足过”)
path(location->a[0]);
else if(“location不为出口”&&“location.a[2]未涉足过”)
path(location->a[0]);
` ````````````````````
``````````
``````
``
else return 0;
}
这是一个迭代过程，需要对每一个方位的位置都遍历一遍，也是一个深度优先的遍历过程。
我在这只给lz一个示意，具体的算法在《数据结构》的书上基本都有，蛮经典的。希望能对lz有所帮组。
加油！
C. 设计算法、编写程序找出由右上角的门进入，由左下角的门离开以下迷宫的路径
//走迷宫
//迷宫的布局可能与你的原图有差异，自己可以修改布局，但不要改迷宫的大小尺寸
//程序仅仅是找出一条可通行的路径，没有作找最优路径的选择。
#include<stdio.h>
inta[20][20];//记录迷宫的布局
intff[4][2]={1,0,-1,0,0,1,0,-1};//行走迷宫的四个方向
intplace[360][2];//记录走的步数
intfx=2,fy=19,tx=18,ty=1;//设置起点(2,19),终点(18,1)
intissame(intn){
inti;
for(i=0;i<n;i++)
if(place[n][0]==place[i][0]&&place[n][1]==place[i][1])
return1;
return0;
}
intnextstep(intn){//迷宫下一步行走
inti,k;
for(i=0;i<4;i++){
place[n][0]=place[n-1][0]+ff[i][0];
place[n][1]=place[n-1][1]+ff[i][1];
if(place[n][0]>19||place[n][0]<1)continue;//行越界
if(place[n][1]>19||place[n][1]<1)continue;//列越界
if(a[place[n][0]][place[n][1]]!=1)continue;//不是1
if(place[n][0]==tx&&place[n][1]==ty)returnn;//到终点
if(issame(n)==1)continue;//走老路
k=nextstep(n+1);
if(k!=0)returnk;
}
return0;
}
intmigong(){//行走迷宫初始化
place[0][0]=fx;place[0][1]=fy;
returnnextstep(1);
}
voidprintit(){//显示迷宫
inti,j;
for(i=1;i<=19;i++){
for(j=1;j<=19;j++)
if(a[i][j]==2)printf("");
elseprintf("%2d",a[i][j]);
printf(" ");
}
}
intmain(){
chars[20][20]={
"0000000000000000000",
"0111111111111111111",
"0000000001000001000",
"0111110101111101111",
"0001010100000100000",
"0101010101110111111",
"0101000100010000010",
"0111111111110111111",
"0100000000010100000",
"0101111111010101111",
"0101000111010101010",
"0111011111010111010",
"0100010000000100010",
"0101011111110101111",
"0101000000010101011",
"0101010101011101011",
"0101010101000001011",
"1101110111111111010",
"0000000000000000000"
};
inti,j,n;
for(i=1;i<=19;i++)
for(j=1;j<=19;j++)
a[i][j]=s[i-1][j-1]-48;
//显示迷宫
printf("原始迷宫模样 ");
printit();
n=migong();
if(n==0)
printf("没有路径到达 ");
else{
for(i=0;i<=n;i++)
a[place[i][0]][place[i][1]]=2;
printf("走迷宫的路径显示 ");
printit();
}
}
D. 求走迷宫的算法！（计算机的算法）（编程也可以
我的思路：
按照人类走迷宫的方法，贴着左边走，左边有路就向左走，左边没路向前走，左边前面都没路向右走
机器人的应该是：1.判断左边是否有墙，无墙：机器人左转，前进一步，继续判断左。。
2.左边有墙，则判断前方是否有墙，无则向前一步，跳回第一步
3.前方有墙（此时状态是左有墙，前有墙），则向机器人右转，跳回第一步
另外有个前提条件，机器人转弯需要原地转，有转弯半径的肯定不行。
还有个问题，就是机器人自己不知道自己已经从迷宫出来了，会一直走。。
E. 罗密欧与朱丽叶的迷宫问题 算法分析与设计
这里已经有了：
http://apps.hi..com/share/detail/12714033
走完迷宫所有的格子,并且转弯次数最少..
在最后找到朱丽叶.
#include<iostream>
using namespace std;
int dir[9][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int count;
int dirs,best;
int board[20][20],bestw[20][20];
int m,n,k;
int sx,sy,ex,ey;
bool comp(int x,int y)
{
if(x>0&&x<=n&&y>0&&y<=m&&board[x][y]==0)
return true;
else return false;
}
void save()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
bestw[i][j]=board[i][j];
}
void search(int dep,int x,int y,int di)
{
if(dep==m*n-k&&x==ex&&y==ey&&dirs<=best)
{
if(dirs<best)
{
best=dirs;
count=1;
save();
}
else count++;
return;
}
if(dep==m*n-k||x==ex&&y==ey||dirs>best) return;
else
{
for(int i=1;i<=8;i++)
if(comp(x+dir[i][0],y+dir[i][1]))
{
board[x+dir[i][0]][y+dir[i][1]]=dep+1;
if(di!=i) dirs++;
search(dep+1,x+dir[i][0],y+dir[i][1],i);
if(di!=i) dirs--;
board[x+dir[i][0]][y+dir[i][1]]=0;
}
}
}
int main()
{
cin>>n>>m>>k;
int i,j;
int c,d;
memset(board,0,sizeof(board));
for(i=0;i<k;i++)
{
cin>>c>>d;
board[c][d]=-1;
}
cin>>sx>>sy;
cin>>ex>>ey;
board[sx][sy]=1;
best=m*n;
dirs=-1;
/***********************
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
cout<<board[i][j]<<" ";
cout<<endl;
}
***********************/
search(1,sx,sy,0);
cout<<best<<endl;
cout<<count<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<bestw[i][j]<<" ";
cout<<endl;
}
}
来自: http://hi..com/dearshawn/blog/item/a4a32eeb2e8277d9d539c90b.html