迷宮演算法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有所幫組。
加油！