迷之演算法

① 迷宮演算法 上下左右 優先順序問題

迷宮一般採用遞歸演算法，而且出口位置在演算法開始時候是不知道的吧。而且迷宮的出口也不會固定到哪一個方向。如果採用枚舉方法一般是按順時針或者逆時針找，這樣才可以用循環來做，如果採用優先，只能將每個方向定位，設一個常量，那樣的話每次遞歸都要判斷一下，非常麻煩，估計還比不用優先還慢一些。

② 求一個簡單的迷宮生成演算法

主要用到了 求並/查找 數據結構，這個結構封裝雀歲在類DisjSets中。這個結構用於區分等價關系，即將一個集合分為多個等價的子集，然後可以對子集求並，或者查找某一元困察素所屬的子集。基本操作很簡單，即union和find兩種。
生成迷宮的演算法是從各處的牆壁開始（入口和出口除外），不斷隨機選擇一面牆，如果被牆分隔的單元不連通，就拆掉該牆，重復此過程直到開始單元和終止單元連通。入口位於左上角，出口位於右下角。
以下是演算法運行生成的某個10階迷宮：

代碼如下：

Cpp代碼
#include <iostream>
#include <頃尺睜vector>
#include <cstdlib>
#include <ctime>

#define N 10

using namespace std;

int wall_row[N+1][N];
int wall_col[N][N+1];

class DisjSets

③ 求java關於迷宮的演算法（用棧實現）

packagecom.Albert.LabyringhStack;

publicclassPoint{
	intx;
	inty;
	intdirection;//direction指向此點附近的一個點應該有四個編號為1234
	publicintgetX(){
		returnx;
	}
	publicvoidsetX(intx){
		this.x=x;
	}
	publicintgetY(){
		returny;
	}
	publicvoidsetY(inty){
		this.y=y;
	}
	
	publicintgetDirection(){
		returndirection;
	}
	publicvoidsetDirection(intdirection){
		this.direction=direction;
	}
	publicvoidaddDirection(){
		this.direction++;
		
	}
	publicPoint(){
	}
	publicPoint(intx,inty){
		super();
		this.x=x;
		this.y=y;
		this.direction=1;
	}
	publicPoint(intx,inty,intdirection){
		super();
		this.x=x;
		this.y=y;
		this.direction=direction;
	}
	
}

packagecom.Albert.LabyringhStack;

importjava.util.*;

publicclassLabyringhStack{

	publicPointS;
	publicPointF;
	char[][]mazemap;
	Stack<Point>path;
	
	publicLabyringhStack(){
	}
	publicLabyringhStack(char[][]ma){//初始化存入數組
		this.mazemap=newchar[ma.length][ma[0].length];
		for(inti=0;i<ma.length;i++){
			for(intj=0;j<ma[0].length;j++){//mazemap[0]必須有元素不可為空
				this.mazemap[i][j]=ma[i][j];
			}
		}
		S=returnPlace('S');
		F=returnPlace('F');
	}
	publicPointreturnPlace(chars){//返回數組中字元的位置
		Pointpoint=newPoint();
		for(inti=0;i<this.mazemap.length;i++){
			for(intj=0;j<this.mazemap[0].length;j++){//mazemap[0]必須有元素不可為空
				if(this.mazemap[i][j]==s)
				{point.setX(i);
					point.setY(j);
					point.setDirection(1);
				}
				}
		}
		returnpoint;
	}
	publiccharreturnChar(Pointpoint){
		if(point.getX()>=0&&point.getY()>=0)
		returnthis.mazemap[point.getX()][point.getY()];
		else
		return'#';
	}
	publicvoidreplacePlace(Pointpoint,chars){//更改特定位置處的字元
		mazemap[point.getX()][point.getY()]=s;
	}
	publicvoidprintPath(){
		Stack<Point>tempPath=newStack<Point>();
		while(!path.empty()){//對棧進行反序
			tempPath.push(path.pop());
		}
		while(!tempPath.empty()){
			System.out.print("("+tempPath.peek().getX()+","+tempPath.pop().getY()+")");
		}
	}
	publicbooleangetPath(){//取得路徑的演算法如果有路徑就返回真
		path=newStack<Point>();
		S.setDirection(1);
		path.push(S);
		replacePlace(S,'X');
		while(!path.empty()){
			PointnowPoint=path.peek();//取得當前位置
			if(nowPoint.getX()==F.getX()&&nowPoint.getY()==F.getY()){
				//printPath();
				returntrue;
			}
			Pointtemp=newPoint();//存放下一個可走的位置
			intfind=0;//標志是否可向下走
			while(nowPoint.getDirection()<5&&find==0){
				switch(nowPoint.getDirection()){
				case1:temp=newPoint(nowPoint.getX(),nowPoint.getY()-1,1);break;//取得當前位置左邊的位置
				case2:temp=newPoint(nowPoint.getX()+1,nowPoint.getY(),1);break;//取得當前位置下邊的位置
				case3:temp=newPoint(nowPoint.getX(),nowPoint.getY()+1,1);break;//取得當前位置右邊的位置
				case4:temp=newPoint(nowPoint.getX()-1,nowPoint.getY(),1);break;//取得當前位置上邊的位置
				}
				nowPoint.addDirection();//指向下一個需要驗證的點
				if(returnChar(temp)=='O'||returnChar(temp)=='F')find=1;//如果能向下走則置為1
			}
				if(find==1){//如果可走就進棧
					replacePlace(temp,'X');//設置成X防止回走
//					printArr();
					path.push(temp);
				}else{//如果不可走就退棧
					replacePlace(nowPoint,'O');
					path.pop();
				}
			}	
		returnfalse;
	}
	publicvoidprintArr(){
		for(inti=0;i<mazemap.length;i++){
			for(intj=0;j<mazemap[0].length;j++){//mazemap[0]必須有元素不可為空
				System.out.print(mazemap[i][j]);
			}
			System.out.println();
		}	
		System.out.println();
	}

}

packagecom.Albert.LabyringhStack;

publicclassMain{

	/**
	*@paramargs
	*/
	publicstaticvoidmain(String[]args){
		//TODOAuto-generatedmethodstub
		char[][]mazemap={
				{'M','M','M','M','M','M','M','M'},
				{'M','S','O','O','M','M','M','M'},
				{'M','M','M','O','M','M','M','M'},
				{'M','M','O','O','O','O','M','M'},
				{'M','M','M','M','M','F','M','M'},
				{'M','M','M','M','M','M','M','M'},
				{'M','M','M','M','M','M','M','M'}
		};
	LabyringhStacksolution=newLabyringhStack(mazemap);
	if(solution.getPath()){
		System.out.print("迷宮路徑如下：");
		solution.printPath();
	}
	else{
		System.out.println("沒有可走的路");
	}
}
}

④ 迷宮演算法中怎麼區分入口和出口

人為標志即可 比如你設入口為1，出口為2，可行進度格子為3，不可行進的為4

⑤ 王者榮耀的迷之匹配機制

王者榮耀的匹配機制分為三種：

1、匹配賽匹衡瞎塵配機制，參考的並不是玩家的段位勝率等因素，而是把玩家打的所有比賽以某種演算法的形式算出一個「綜合分」，這個綜合分又被叫做隱藏分數，盡最大可能代表一個人的最真實實力。

2、賞金賽的匹配機神蘆制，採用的是一種難度遞進的機制，就是像闖關一樣，一關比一關難。

3、排位賽匹配機制，單排，雙排，三排都是按照隊伍平均段位水平去匹配，五排是按照五個咐禪人中最高的段位去匹配，一般情況下，黃金雙排不會遇到鉑金玩家，除非是另外幾個人里有鉑金，而假設對面有三鉑金，說明該玩家這邊至少有對應的段位。

⑥ 急！設計一個迷宮演算法，從文件中讀取，開頭的第一行數字表示行，列，但總輸不出答案。請求幫助！

和健康健康的空間按時間阿卡

⑦ 迷宮演算法復雜度如何計算

迷宮生成可以O(n*m)完成。走迷宮的話可以O(n*m*2)左右。
只要記錄走到每一格的最優解就可以了。
最好不要用深度優先搜索。用廣度優先的實現方便。

⑧ 求走迷宮的演算法！（計算機的演算法）（編程也可以

我的思路：
按照人類走迷宮的方法，貼著左邊走，左邊有路就向左走，左邊沒路向前走，左邊前面都沒路向右走

機器人的應該是：1.判斷左邊是否有牆，無牆：機器人左轉，前進一步，繼續判斷左。。
2.左邊有牆，則判斷前方是否有牆，無則向前一步，跳回第一步
3.前方有牆（此時狀態是左有牆，前有牆），則向機器人右轉，跳回第一步
另外有個前提條件，機器人轉彎需要原地轉，有轉彎半徑的肯定不行。
還有個問題，就是機器人自己不知道自己已經從迷宮出來了，會一直走。。

⑨ 簡單的迷宮演算法

用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)

⑩ 迷宮演算法

#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");
}