迷之算法

① 迷宫算法 上下左右 优先级问题

迷宫一般采用递归算法，而且出口位置在算法开始时候是不知道的吧。而且迷宫的出口也不会固定到哪一个方向。如果采用枚举方法一般是按顺时针或者逆时针找，这样才可以用循环来做，如果采用优先，只能将每个方向定位，设一个常量，那样的话每次递归都要判断一下，非常麻烦，估计还比不用优先还慢一些。

② 求一个简单的迷宫生成算法

主要用到了 求并/查找 数据结构，这个结构封装雀岁在类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");
}