机械迷城第7关移动箭头小游戏解法 机械迷城箭头

前阵子刚把机械迷城玩通关,个人感觉是一款非常不错的游戏。游戏里内置了很多有意思的小游戏,游戏虽小但想快速通关还是有一定难度的。正好本人最近没啥事情,于是想尝试编写一些C程序以求解每个小游戏,纯属个人娱乐不喜勿喷!

首先从第七关移动箭头这个小游戏下手,游戏画面如下图左上角所示,中间一个空白按钮,空白按钮上面是三个向下的箭头,下面是三个向上箭头。游戏的最终目标是把下面的三个箭头移到上面三个位置,同时上面三个移到下面,如下图右下角所示。



游戏规则是这样的:移动方式是某个箭头与空白按钮换位,但是空白按钮只能与邻近的上下距离不超过2的按钮换位,而且指向朝下的箭头只能向下移,指向朝上的箭头只能向上移动;同时在越按钮移动时,如果待移动的按钮和它跟空白按钮之间的按钮的指向一致是不允许移动的,如下图所示:


只要掌握了规律,操作起来是很简单的,但是让计算机来办这事似乎有些难度,既然计算机不具备推理能力,那只有施展其计算速度快的有点了。该问题具有三个量:上下箭头和空白按钮,所以编码方式至少能表示这三个量,在此选择[1,0,-1]分别表示[向下箭头,空白,向上箭头]。每次移动空白按钮都要参与,移动的方式共有四种(表示为0,1,2,3),上下交换和越按钮交换,当然不是每种移动方式都遵守规则,需要相应的判断语句。程序的算法与迷宫问题非常相似,求解的过程正好构成一个栈结构,基本过程是这样的,找到空白按钮的位置,从方式0开始查找可行的移动方式,如果方式0违反规则则更换方式1以此进行,如果找到符合规则的移动方式则移动之后入栈,并且重复上述步骤,如果4种移动方式均违反规则,首先判断此时的状态是否已经达到最终要求,如果没有达到则出栈,算法循环进行下去直到找到最终解。以下是具体的C代码:

#include <stdio.h>

#define ARROW_LENGTH3//定义朝下的箭头的数量,与朝上的箭头数量相同
#define MAX_STACK_LENGTH(ARROW_LENGTH*ARROW_LENGTH+2*ARROW_LENGTH+1)//定义栈的大小,关系为y=x*x+2*x,另外多加一个以防不足

//定义栈单元结构
typedef struct
{
int arrow[2*ARROW_LENGTH+1];//记录移动之后的状态
int position; //记录空白按钮的位置
int dir; //记录移动方式,共四种
}element;

element stack[MAX_STACK_LENGTH]; //声明需要的栈
int usedMaxStackLength=0; //统计计算过程中需要的栈的最大长度

//入栈操作
int add(int *top, element item)
{
if(*top >=MAX_STACK_LENGTH-1)
{
return -1;
}
stack[++*top] = item;
if((*top)>usedMaxStackLength)
usedMaxStackLength =*top;
return 0;
}
//出栈操作
int delete(int *top, element *item)
{
if(*top == -1)
{
return -1;
}
item = &stack[(*top)--];
return 0;
}

//打印一个数组
void PrintArray(int *array,int length)
{
int i,temp;
for(i=0;i<length;i++)
{
temp = *(array+i);
printf("%d ",temp);
}
printf("n");
}
//打印整个栈
void PrintStack(int *top)
{
int i;
for(i=*top;i>=0;i--)
{
printf("ID=%d,Value=%d,Array=",i,stack[i].position);
PrintArray(stack[i].arrow,sizeof(stack[i].arrow)/sizeof(int));
}
}
//拷贝数据
int CopyArray(int *target,int *source,int target_length,intsource_length)
{
int i;
if(source_length >target_length)
{
return -1;
}
for(i=0;i<source_length;i++)
{
*(target+i) =*(source+i);
}
return 0;
}
//初始化箭头的状态
void InitialTempArrow(int *ptr,int length)
{
int i;
for(i=0;i<length;i++)
*(ptr+i) =1;
*(ptr+length) = 0;
for(i=length+1;i<(2*length+1);i++)
*(ptr+i) = -1;
}
//记录箭头的最终状态
void InitialTargetArrow(int *ptr,int length)
{
int i;
for(i=0;i<length;i++)
*(ptr+i) =-1;
*(ptr+length) = 0;
for(i=length+1;i<(2*length+1);i++)
*(ptr+i) = 1;
}
//比较两个数组是否相等
int CompareArray(int *target,int *source,int length_target,intlength_source)
{
int i;
if(length_target != length_source)
return -1;
else
{
for(i=0;i<length_target;i++)
{
if(*(target+i)!= *(source+i))
return-1;
}
return 0;
}
}
//算法核心
void CalcutePath(void)
{
element temp_element;
int temp_arrow[2*ARROW_LENGTH+1];
int target_arrow[2*ARROW_LENGTH+1];
int top = -1;
int found = 0;
int state,push_state;
int temp_data;
InitialTempArrow(temp_arrow,ARROW_LENGTH);
InitialTargetArrow(target_arrow,ARROW_LENGTH);
CopyArray(temp_element.arrow,temp_arrow,sizeof(temp_element.arrow)/sizeof(int),sizeof(temp_arrow)/sizeof(int));
temp_element.position = ARROW_LENGTH;
temp_element.dir = 0;
state =add(&top,temp_element);
if(state<0)
{
printf("Push failed!n");
return;
}
while(top>-1&& !found)
{
push_state = 0;
temp_element =stack[top];
while(temp_element.dir<4&& !push_state)
{
//switch下包含了四种移动方式
switch(temp_element.dir)
{
case0:
if(temp_element.position>1&&temp_element.arrow[temp_element.position-2]>0&&temp_element.arrow[temp_element.position-1]<0)
{
push_state= 1;
temp_data= temp_element.arrow[temp_element.position];
temp_element.arrow[temp_element.position]= temp_element.arrow[temp_element.position-2];
temp_element.arrow[temp_element.position-2]= temp_data;
temp_element.position= temp_element.position - 2;
temp_element.dir= 0;
state= add(&top,temp_element);
}
else
机械迷城第7关移动箭头小游戏解法 机械迷城箭头
temp_element.dir++;
break;
case1:
if(temp_element.position>0&&temp_element.arrow[temp_element.position-1]>0)
{
push_state= 1;
temp_data= temp_element.arrow[temp_element.position];
temp_element.arrow[temp_element.position]= temp_element.arrow[temp_element.position-1];
temp_element.arrow[temp_element.position-1]= temp_data;
temp_element.position= temp_element.position - 1;
temp_element.dir= 0;
state= add(&top,temp_element);
}
else
temp_element.dir++;
break;
case2:
if(temp_element.position<2*ARROW_LENGTH&&temp_element.arrow[temp_element.position+1]<0)
{
push_state= 1;
temp_data= temp_element.arrow[temp_element.position];
temp_element.arrow[temp_element.position]= temp_element.arrow[temp_element.position+1];
temp_element.arrow[temp_element.position+1]= temp_data;
temp_element.position= temp_element.position + 1;
temp_element.dir= 0;
state= add(&top,temp_element);
}
else
temp_element.dir++;
break;
case3:
if(temp_element.position<2*ARROW_LENGTH&&temp_element.arrow[temp_element.position+2]<0&&temp_element.arrow[temp_element.position+1]>0)
{
push_state= 1;
temp_data= temp_element.arrow[temp_element.position];
temp_element.arrow[temp_element.position]= temp_element.arrow[temp_element.position+2];
temp_element.arrow[temp_element.position+2]= temp_data;
temp_element.position= temp_element.position + 2;
temp_element.dir= 0;
state= add(&top,temp_element);
}
else
temp_element.dir++;
break;
default:
break;
}
}
if(push_state == 1)
{
push_state =0;
}
elseif(CompareArray(target_arrow,temp_element.arrow,sizeof(target_arrow)/sizeof(int),sizeof(temp_element.arrow)/sizeof(int))==0)
{
found = 1;//找到最终结果
}
else
{
state =delete(&top,&temp_element);//出栈
if(state<0)
{
printf("Popfailed!n");
return;
}
stack[top].dir++;
}
}

if(found == 1)
{
PrintStack(&top);
}
else
printf("Some Error!n");
}

int main()
{
CalcutePath();
printf("Used stacksize=%dn",usedMaxStackLength);
return 0;
}
以上代码可以在任何平台上运行,开始语句#define ARROW_LENGTH定义箭头的数量,大小可以随意改变,但是至少为1,如果过大则计算过程会偏长。

定义箭头数量为3,ubuntu下运行结果如下:





定义箭头数量为5,运行结果如下:




  

爱华网本文地址 » http://www.aihuau.com/a/25101013/162155.html

更多阅读

《机械迷城》第七关图文攻略 迷城的国度图文攻略

出门来,右边河太远,过不了,只能向左走.左走来发现前面漏水了。机器人最怕水,正好旁边有一位打伞的机器人大妈,和她交谈,得知想要她的伞必须要用狗来换,向回走,发现狗正躲在对面的角落里找东西吃,想抓到狗就要先把它引出来《机械迷城》第七关

寻找懂球帝第六关答案 寻找懂球帝动态福利图

寻找懂球帝第六关答案——简介网易寻找懂球帝第六关答案寻找懂球帝第六关答案——工具/原料智能手机、网易新闻客户端、寻找懂球帝第六关答案——方法/步骤寻找懂球帝第六关答案 1、1、“足球不是生死,但高于生死”这句名言是谁说

qq飞车闪耀的皇族第7关怎么过 qq飞车燕子坞最快跑法

qq飞车闪耀的皇族第7关怎么过——简介主要是在多练习 , 首先不能有失误,最重要的是近道是关键。第一圈别用计时跑法,也就是视频那种。有气就W喷放了。我刚到第二圈就放气超了他们。只后不失误就行了。很抱歉,视频数据暂时无法显示

《使命召唤8》第二章图文攻略第1关 使命召唤5图文攻略

中文名: 使命召唤:现代战争3 外文名: Call of Duty : Modern Warfare 3 游戏类别: 第一人称射击、FPS 游戏平台: X360、PS3、PC 开发商: Sledgehammer Games 发行商: 动视暴雪 发行时间: 2011年11月8日 《使命召唤8》第二章图文攻略(第1关)—

钉子户大战拆迁队第2关 钉子户大战搬迁队无敌

传说中的钉子户和游戏中的有什么区别呢,我们怎么去战胜拆迁队呢,如何保护自己的家园呢,一起来看看吧!钉子户大战拆迁队第2关——工具/原料拆屋大战单机游戏钉子户大战拆迁队第2关——步骤/方法钉子户大战拆迁队第2关 1、一开始拆迁队就

声明:《机械迷城第7关移动箭头小游戏解法 机械迷城箭头》为网友狂神分享!如侵犯到您的合法权益请联系我们删除