迷宫算法a
示例：
#coding:UTF-8
globalm,n,path,minpath,pathnum
m=7
n=7
k=[0,1,2,3,4,5,6,7]#循环变量取值范围向量
a=[[0,0,1,0,0,0,0,0],
[1,0,1,0,1,1,1,0],
[0,0,0,0,1,0,0,0],
[1,1,1,1,1,0,0,0],
[0,0,0,0,0,1,1,0],
[0,0,0,0,0,0,0,0],
[0,0,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0]]#迷宫矩阵
b=[[1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]] #状态矩阵
path=[]
minpath=[]
min=10000
step=0
pathnum=0
#print(a)
#print(b)
defnextone(x,y):
globalpath,minpath,m,n,min,step,pathnum
if(x==0)and(y==0):
path=[]
step=0
if(x==m)and(y==n):
pathnum+=1
print("step=",step)
print("path=",path)
ifstep<min:
min=step
minpath=path[:]
else:
if(x+1ink)and(yink):
if(b[x+1][y]==0)and(a[x+1][y]==0):
b[x+1][y]=1
path.append([x+1,y])
step+=1
nextone(x+1,y)
step-=1
path.remove([x+1,y])
b[x+1][y]=0#回溯
if(xink)and(y+1ink):
if(b[x][y+1]==0)and(a[x][y+1]==0):
b[x][y+1]=1
path.append([x,y+1])
step+=1
nextone(x,y+1)
step-=1
path.remove([x,y+1])
b[x][y+1]=0#回溯
if(x-1ink)and(yink):
if(b[x-1][y]==0)and(a[x-1][y]==0):
b[x-1][y]=1
path.append([x-1,y])
step+=1
nextone(x-1,y)
step-=1
path.remove([x-1,y])
b[x-1][y]=0#回溯
if(xink)and(y-1ink):
if(b[x][y-1]==0)and(a[x][y-1]==0):
b[x][y-1]=1
path.append([x,y-1])
step+=1
nextone(x,y-1)
step-=1
path.remove([x,y-1])
b[x][y-1]=0#回溯
nextone(0,0)
print()
print("min=",min)
print("minpath=",minpath)
print("pathnum=",pathnum)
B. 简单的迷宫算法
用python递归求解
dirs=[(0,1),(1,0),(0,-1),(-1,0)] #当前位置四个方向的偏移量
path=[] #存找到的路径
def mark(maze,pos): #给迷宫maze的位置pos标"2"表示“倒过了”
maze[pos[0]][pos[1]]=2
def passable(maze,pos): #检查迷宫maze的位置pos是否可通行
return maze[pos[0]][pos[1]]==0
def find_path(maze,pos,end):
mark(maze,pos)
if pos==end:
print(pos,end=" ") #已到达出口，输出这个位置。成功结束
path.append(pos)
return True
for i in range(4): #否则按四个方向顺序检查
nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1]
#考虑下一个可能方向
if passable(maze,nextp): #不可行的相邻位置不管
if find_path(maze,nextp,end):#如果从nextp可达出口，输出这个位置，成功结束
print(pos,end=" ")
path.append(pos)
return True
return False
def see_path(maze,path): #使寻找到的路径可视化
for i,p in enumerate(path):
if i==0:
maze[p[0]][p[1]] ="E"
elif i==len(path)-1:
maze[p[0]][p[1]]="S"
else:
maze[p[0]][p[1]] =3
print("\n")
for r in maze:
for c in r:
if c==3:
print('\033[0;31m'+"*"+" "+'\033[0m',end="")
elif c=="S" or c=="E":
print('\033[0;34m'+c+" " + '\033[0m', end="")
elif c==2:
print('\033[0;32m'+"#"+" "+'\033[0m',end="")
elif c==1:
print('\033[0;;40m'+" "*2+'\033[0m',end="")
else:
print(" "*2,end="")
print()
if __name__ == '__main__':
maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\
[1,0,0,0,1,1,0,0,0,1,0,0,0,1],\
[1,0,1,0,0,0,0,1,0,1,0,1,0,1],\
[1,0,1,0,1,1,1,1,0,1,0,1,0,1],\
[1,0,1,0,0,0,0,0,0,1,1,1,0,1],\
[1,0,1,1,1,1,1,1,1,1,0,0,0,1],\
[1,0,1,0,0,0,0,0,0,0,0,1,0,1],\
[1,0,0,0,1,1,1,0,1,0,1,1,0,1],\
[1,0,1,0,1,0,1,0,1,0,1,0,0,1],\
[1,0,1,0,1,0,1,0,1,1,1,1,0,1],\
[1,0,1,0,0,0,1,0,0,1,0,0,0,1],\
[1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
start=(1,1)
end=(10,12)
find_path(maze,start,end)
see_path(maze,path)
C. A* 算法求解迷宫寻路问题
我不想说出来我是刷的
D. 迷宫问题详细的算法或Pascal程序带注释
Dinic算法的思想是为了减少增广次数，建立一个辅助网络L，L与原网络G具有相同的节点数，但边上的容量有所不同，在L上进行增广，将增广后的流值回写到原网络上，再建立当前网络的辅助网络，如此反复，达到最大流。分层的目的是降低寻找增广路的代价。
算法步骤如下：
STEP1：建造原网络G的一个分层网络L。
STEP2：用增广路算法计算L的最大流F，若在L中找不到增广路，算法结束。
SETP3：根据F更新G中的流f，转STEP1。
分层网络的构造算法：
STEP1：标号源节点s，M[s]＝0。
STEP2：调用广度优先遍历算法，执行一步遍历操作，当前遍历的弧e=v1v2，令r＝G.u（e）－G.f（e）。
若r>0，则
（1） 若M[v2]还没有遍历，则M[v2]=M[v1]+1，且将弧e加入到L中，容量L.u（e）＝r。
（2） 若M[v2]已经遍历且M[v2]=M[v1]+1，则将边e加入到L中，容量L.u（e）＝r。
（3） 否则L.u（e）＝0。
否则L.u（e）＝0。
重复本步直至G遍历完。其中的G.u(e)、G.f(e)、L.u(e)分别表示图G中弧e的容量上界和当前流量，图L中弧e的容量上界。
下附程序 （邻接表的程序，希望看得懂）
Program zw_dinicc;
type
o=record
point,next,c:longint;
end;
Var
i,j,k,p,n,m,head,tail,s,t,tot,a1,a2,a3,tot1,a4:longint;
h,l:array[1..55002]of longint;
first:array[1..55002]of longint;
e:array[1..310002] of o;
procere add(a,b,c:longint);
begin
e[tot1].point:=b; e[tot1].next:=first[a]; e[tot1].c:=c; first[a]:=tot1; inc(tot1);
end;
procere init;
var i,x,y,q:longint;
begin
tot1:=2;
readln(n,m);
for i:=m+2 to n+m+1 do
begin
read(a1);
add(i,n+m+2,a1);
add(n+m+2,i,0);
end;
for i:=2 to m+1 do
begin
read(a1,a2,a3);
add(i,1+m+a1,65536000); add(1+m+a1,i,0);
add(i,1+m+a2,65536000); add(1+m+a2,i,0);
add(1,i,a3);add(i,1,0);
inc(j,a3);
end;
n:=2+m+n;
s:=1;
t:=n;
end;
//以上为建边，用的是残量网络
procere bfs;｛构建分层图，从原点开始广搜｝
var
i,j,k,now:longint;
begin
head:=1; tail:=1; l[head]:=s; fillchar(h,sizeof(h),127); h[s]:=0;
while head<= tail do
begin
now:=l[head]; inc(head); k:=first[now];
while k>0 do
begin
if (h[e[k].point]>n) and(e[k].c>0) then｛如果可以流，且该点未被访问｝
begin
h[e[k].point]:=h[now]+1;
inc(tail);
l[tail]:=e[k].point;
end;
k:=e[k].next;
end;
end;
end;
function dfs(now,low:longint):longint;｛根据分层图增广，low表示到now为止最多可增广流量｝
var
i,j,k,tmp:longint;
begin
if now=t then exit(low);
dfs:=0; k:=first[now];
while k>0 do
begin
if (e[k].c>0) and (h[e[k].point]=h[now]+1) then｛如果在分层图中符合限制｝
begin
if e[k].c<low then tmp:=dfs(e[k].point,e[k].c)｛寻找可接受的最大流量｝
else tmp:=dfs(e[k].point,low);
if tmp=0 then h[e[k].point]:=maxlongint shr 1;
dec(low,tmp);｛把可流量减去增广值｝
dec(e[k].c,tmp);
inc(e[k xor 1].c,tmp);
inc(dfs,tmp);
if low=0 then break;｛若无法再增广，退出｝
end;
k:=e[k].next;
end;
end;
Procere main;
begin
bfs;
while h[t]<n do｛如果在分层图中找得到汇点｝
begin
inc(tot,dfs(s,maxlongint));｛根据分层图增广｝
bfs;｛根据新的流量构建分层图｝
end;
end;
Begin
assign(input,'profit.in');reset(input);
assign(output,'profit.out');rewrite(output);
init;
main;
writeln(j-tot);
close(input);close(output);
End.
看在本人手打这么多东西的份上，选我吧
E. 迷宫算法
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定义迷宫内点的坐标类型
{
int x;
int y;
};
struct Element //"恋"栈元素，嘿嘿。。
{
int x,y; //x行,y列
int d; //d下一步的方向
};
typedef struct LStack //链栈
{
Element elem;
struct LStack *next;
}*PLStack;
/*************栈函数****************/
int InitStack(PLStack &S)//构造空栈
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判断栈是否为空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//压入新数据元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //栈顶元素出栈
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宫路径函数***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //开始为-1
Push(S1,elem);
while(!StackEmpty(S1)) //栈不为空 有路径可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一个方向
while(d<4) //试探东南西北各个方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴o(∩_∩)o...
}
if(maze[a][b]==0) //找到可以前进的非出口的点
{
maze[a][b]=2; //标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //当前位置入栈
i=a; //下一点转化为当前点
j=b;
d=-1;
}
d++;
}
}
printf("没有找到可以走出此迷宫的路径\n");
}
/*************建立迷宫*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宫行,列
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为o(∩_∩)o...\n");
for(i=0;i<=m+1;i++) //加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北
initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}
F. 25格迷宫的0-1矩阵为00100 01010 01100 00110 11010,求c语言解出一条通过迷宫的路径。
你这个题意表述得不是很完整。首先，这个迷宫的出口和入口坐标分别是哪个？也就是迷宫的起点和终点在哪？第二，行走的规则是什么？是只能横竖走？还是也可以斜着走。
然后像这类的寻路有一种很好的算法叫A*寻路算法，你可以自己网络一下。大致的思路是从起点开始，维护两个表。第一个表是下一步可以到达的格子属性表，这个表中每个格子至少要有权值（也就是预计离目标远近的值）和父节点2个属性，而且必须按权值顺序排序。另外一个表是已经寻过路的格子。讲起来有点复杂，但做起来不是太难。网络一下吧。
G. A*path与Dijkstra寻路、迷宫生成
假设有人想从 A 点移动到一墙之隔的 B 点，如下图，绿色的是起点 A，红色是终点 B，蓝色方块是中间的墙。
在 A*寻路算法中，我们通过从绿色起点 A 开始，检查相邻方格的方式，向外扩展直到找到目标。
我们做如下操作开始搜索：
通常对于方格节点，我们认为水平/垂直移动一格耗费为 10，对角线移动耗费为 14。
G = 从 起点 沿着生成的路径，移动到当前节点的总移动耗费。
H = 从当前节点移动到 终点 的移动耗费估算。这经常被称为启发式的，因为它只是个猜测，我们没办法事先知道路径的实际长度。
对于方格节点通常使用 曼哈顿方法 ，它计算从当前格到 终点 之间水平和垂直的方格的数量总和，忽略对角线方向和障碍物。然后把结果乘以水平/垂直的移动耗费。
对于允许走对角线的节点使用 对角线方法 ，允许任意走的节点使用 欧几里得方法
当H值总为0时，退化为Dijkstra寻路算法
先构建一个如下的模型图,其中黑色为墙壁,红色为路径节点。墙可以为一个方形格子也可以仅仅是一条线(为方格时对角线上的墙壁始终无法被打通)。
先构建一个除了外圈为黑色墙壁,内部全是灰色通路的迷宫模型
H. 数据结构中，求解迷宫问题的程序算法，，，
// test_03.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
using namespace std;
struct PosType /* 迷宫坐标位置类型 */
{
int x; /* 行值 */
int y; /* 列值 */
};
int Maze[5][5] =
{
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};
#define MAXLENGTH 5
int curstep=1;
int a[MAXLENGTH];
int b[MAXLENGTH];
struct SElemType/* 栈的元素类型 */
{
int ord; /* 通道块在路径上的＂序号＂ */
PosType seat; /* 通道块在迷宫中的＂坐标位置＂ */
int di; /* 从此通道块走向下一通道块的＂方向＂(0～3表示东～北) */
};
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
struct SqStack //SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}; /* 顺序栈 */
bool InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
{
exit(1); /* 存储分配失败 */
}
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return true;
}
bool Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
{
exit(1); /* 存储分配失败 */
}
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return true;
}
bool StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return true;
else
return false;
}
bool Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return false;
*e=*(--(*S).top);
return true;
}
bool Pass(PosType b)
{ /* 当迷宫m的b点的序号为1(可通过路径)，return true, 否则，return false */
if(Maze[b.x][b.y]==1)
return true;
else
return false;
}
void FootPrint(PosType a)
{ /* 使迷宫m的a点的序号变为足迹(curstep) */
Maze[a.x][a.y]=curstep;
}
PosType NextPos(PosType c,int di)
{ /* 根据当前位置及移动方向，返回下一位置 */
PosType direc[4]={{0,1},{1,0},{-1,0},{0,-1}};
/* 移动方向,依次为东南西北 */
c.x+=direc[di].x;
c.y+=direc[di].y;
return c;
}
void MarkPrint(PosType b)
{ /* 使迷宫m的b点的序号变为-1(不能通过的路径) */
Maze[b.x][b.y]=-1;
}
void Print(int x,int y)
{ /* 输出迷宫的解 */
int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
cout<<"\t"<<Maze[i][j];
cout<<endl;
}
}
bool MazePath(PosType start,PosType end)
{
SqStack S;
SElemType e;
InitStack(&S);
a[0]=start.x;
b[0]=start.y;
PosType curpos=start;
do
{
if(Pass(curpos))
{ /* 当前位置可以通过，即是未曾走到过的通道块 */
FootPrint(curpos); /* 留下足迹 */
a[curstep]=curpos.x;
b[curstep]=curpos.y;
e.di=0;
e.ord=curstep;
e.seat.x=curpos.x;
e.seat.y=curpos.y;
Push(&S,e);
// printf("PUSH1 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord);
if(curpos.x==end.x&&curpos.y==end.y)
return true;
curpos=NextPos(curpos,e.di);
curstep++;
}
else
{ /* 当前位置不能通过 */
if(!StackEmpty(S))
{
Pop(&S,&e); /* 退栈到前一位置 */
// printf("POP1 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord);
curstep--;
while((e.di==3) && (!StackEmpty(S)))
{
MarkPrint(e.seat);
Pop(&S,&e);
printf("POP2 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord);
curstep--;
}
if(e.di<3) /* 没到最后一个方向(北) */
{
e.di++;
// e.seat.x=curpos.x;
// e.seat.y=curpos.y;
Push(&S,e);
// printf("PUSH2 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord);
curpos=NextPos(e.seat,e.di);
curstep++;
}
}
}
}while(!StackEmpty(S));
return false;
}
int _tmain(int argc, _TCHAR* argv[])
{
PosType begin,end;
begin.x = 1;
begin.y = 1;
end.x = 3;
end.y = 3;
if(MazePath(begin,end)) /* 求得一条通路 */
{
cout<<"此迷宫从入口到出口的一条路径如下:"<<endl;
Print(5,5); /* 输出此通路 */
for(int i=1;i<curstep;i++)
{
cout<<"("<<a[i]<<","<<b[i]<<")"<<"->";
}
cout<<"("<<a[curstep]<<","<<b[curstep]<<")"<<endl;
}
else
{
cout<<"此迷宫没有从入口到出口的路径"<<endl;
}
system("pause");
return 0;
}
I. 用C/C++编写迷宫，用A*算法
#include "stdafx.h"
#include <stack>
using namespace std;
//定义常数
const int rows = 8,cols = 8;
//声明全局变量�
HINSTANCE hInst;
HBITMAP ball;
HDC hdc,mdc,bufdc;
HWND hWnd;
DWORD tPre,tNow;
char *str;//记录目前搜索状态的字符串指针
int nowPos,prePos;
bool find;//声明一个布尔变量，以记录是否找到迷宫出口
stack<int> path;//建立一个整型堆栈path
int mapIndex[rows*cols] = { 0,2,0,0,0,0,0,0,
0,1,0,1,1,1,1,0,
0,1,0,1,0,1,1,0,
0,1,0,0,0,1,1,0,
0,1,1,1,1,1,1,0,
0,1,0,0,0,0,1,0,
0,0,1,1,1,1,1,0,
0,0,0,0,0,0,3,0 };
int record[rows*cols];
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
void MyPaint(HDC hdc);
int APIENTRY WinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR lpCmdLine,
int nCmdShow)
{
MSG msg;
MyRegisterClass(hInstance);
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
while( msg.message!=WM_QUIT )
{
if( PeekMessage( &msg, NULL, 0,0 ,PM_REMOVE) )
{
TranslateMessage( &msg );
DispatchMessage( &msg );
}
else
{
tNow = GetTickCount();
if(tNow-tPre >= 100)
MyPaint(hdc);
}
}
return msg.wParam;
}
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = (WNDPROC)WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = NULL;
wcex.hCursor = NULL;
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = NULL;
wcex.lpszClassName = "canvas";
wcex.hIconSm = NULL;
return RegisterClassEx(&wcex);
}
//*****************************************
// 1.迷宫拼接地图
// 2.设定小球在迷宫入口处
// 3.按照mapIndex设定record数组的初始内容
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
HBITMAP bmp;
hInst = hInstance;
hWnd = CreateWindow("canvas", "迷宫" , WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
if (!hWnd)
{
return FALSE;
}
MoveWindow(hWnd,10,10,430,450,true);
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
hdc = GetDC(hWnd);
mdc = CreateCompatibleDC(hdc);
bufdc = CreateCompatibleDC(hdc);
bmp = CreateCompatibleBitmap(hdc,cols*50,rows*50);
SelectObject(mdc,bmp);
HBITMAP tile;
int rowNum,colNum;
int i,x,y;
//加载位图
tile = (HBITMAP)LoadImage(NULL,"tile.bmp",IMAGE_BITMAP,50,50,LR_LOADFROMFILE);
ball = (HBITMAP)LoadImage(NULL,"ball.bmp",IMAGE_BITMAP,50,50,LR_LOADFROMFILE);
for (i=0;i<rows*cols;i++)
{
record[i] = mapIndex[i];
rowNum = i / cols; //求列编号
colNum = i % cols; //求行编号
x = colNum * 50; //求贴图X坐标
y = rowNum * 50; //求贴图Y坐标
SelectObject(bufdc,tile);
if(!mapIndex[i]) //如果是0，就贴墙
BitBlt(mdc,x,y,50,50,bufdc,0,0,SRCCOPY);
else //通道
{
if(mapIndex[i] == 2) //找到迷宫出口
{
nowPos = i;
path.push(i);
record[i] = 0;
}
BitBlt(mdc,x,y,50,50,bufdc,0,0,WHITENESS);//WHITENESS 白色50*50的方块
}
}
prePos = cols * rows + 1;
MyPaint(hdc);
return TRUE;
}
//*************************************
// 搜寻可行走路径及小球移动贴图
void MyPaint(HDC hdc)
{
int rowNum,colNum;
int x,y;
int up,down,left,right;
//清除上次贴图
rowNum = prePos / cols;
colNum = prePos % cols;
x = colNum * 50;
y = rowNum * 50;
SelectObject(bufdc,ball);
BitBlt(mdc,x,y,50,50,bufdc,0,0, WHITENESS);
//贴小球
rowNum = nowPos / cols;
colNum = nowPos % cols;
x = colNum * 50;
y = rowNum * 50;
SelectObject(bufdc,ball);
BitBlt(mdc,x,y,50,50,bufdc,0,0, SRCCOPY);
if(!find)
{
str = "搜寻出口中...";
up = nowPos - cols;
down = nowPos + cols;
left = nowPos - 1;
right = nowPos + 1;
if(up>=0 && record[up]) //往上走�
{
path.push(up);
record[up] = 0;
prePos = nowPos;
nowPos = up;
if(mapIndex[nowPos] == 3) //找到出口
find = true;
}
else if(down<=cols*rows-1 && record[down]) //下
{
path.push(down);
record[down] = 0;
prePos = nowPos;
nowPos = down;
if(mapIndex[nowPos] == 3)
find = true;
}
else if(left>=rowNum*cols && record[left]) //左
{
path.push(left);
record[left] = 0;
prePos = nowPos;
nowPos = left;
if(mapIndex[nowPos] == 3)
find = true;
}
else if(right<=(rowNum+1)*cols-1 && record[right]) //右
{
path.push(right);
record[right] = 0;
prePos = nowPos;
nowPos = right;
if(mapIndex[nowPos] == 3)
find = true;
}
else //无�
{
if(path.size() <= 1) //回到入口����
str = "迷宫没有出口...";
else
{
path.pop();
prePos = nowPos;
nowPos = path.top();
}
}
}
else
{
str = "找到出口了!";
}
TextOut(mdc,0,0,str,strlen(str));
BitBlt(hdc,10,10,cols*50,rows*50,mdc,0,0,SRCCOPY);
tPre = GetTickCount();
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
switch (message)
{
case WM_KEYDOWN:
if(wParam==VK_ESCAPE)
PostQuitMessage(0);
break;
case WM_DESTROY:
DeleteDC(mdc);
DeleteDC(bufdc);
DeleteObject(ball);
ReleaseDC(hWnd,hdc);
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
J. 试设计迷宫求解算法:迷宫是一个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有所帮组。
加油！