演算法設計迷宮

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