爱华网前阵子刚把机械迷城玩通关，个人感觉是一款非常不错的游戏。游戏里内置了很多有意思的小游戏，游戏虽小但想快速通关还是有一定难度的。正好本人最近没啥事情，于是想尝试编写一些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
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，运行结果如下：
