【A*算法】滑动积木游戏

滑动积木块游戏

Description

滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如图1所示。

图1. 3滑块游戏的初始格局

其中，B表示黑色将牌，W表示白色将牌，E表示空格。我们称将牌的排列结构称为格局，而根据单色将牌的个数，将游戏分别称为3滑块或4滑块游戏等。所以，上图就是3滑块游戏的初始格局。我们可以用字符串来代表格局，代表上图中初始格局的字符串为BBBWWWE。

游戏的规定走法是：

①     任意一个将牌可以移入相邻的空格，规定其耗散值（代价）为1。

②     任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目。

游戏要达到的目标是使所有白将牌都处在黑将牌的左边（左边有无空格均可），我们称为目标格局。很显然，3滑块游戏的目标格局共有7种。

随着将牌的移动，我们会得到一些中间格局，例如：

图2. 3滑块游戏的某个中间格局

对于某个格局，通过一次移动滑块而得到的格局，称为其后继格局。我们需要找到某个中间格局的所有后继格局，即每种可能的走法所能得到的格局，并计算得到这个格局的代价。同时，为了尽快到达目标格局，我们需要对这些后继格局进行评价，找出一个可能最先到达目标格局的。一个可行的评价函数是在每个W前的B的个数的和。根据这个评价函数，图1中的格局的评价值为9，图2中的格局的评价值为8。

Input

    输入的第一行是一个整数N, 表示共有N个格局。后续紧跟N行，每行由两部分构成，第一部分是一个整数n，表示这是一个n滑块游戏，第二部分是  2n+1个字符，表示该游戏的某个格局。

Output

    首先判断输入的格局是否是目标格局，如果是，则输出“目标格局”后结束；如果不是目标格局，则按顺序（将格局看做字符串后，按照字典序排序，即W > E > B）输出该格局的所有后继格局，耗散值和评价函数值。例如，BBEBWWW 格局应该排在 BBWBWEW 格局的前面，因为在英文字母表中，第一个格局中的第3个字符E排在第二个格局的第3个字符W前面

Sample Iput

3    BBWBEWW

Sample Output

程序代码：

#include
#include
using namespace std;
int evaluation(char *n);             //评价函数声明;
struct pt
{char *a1;//存储处理后的字符数组;                                           int hs;  //耗散值;int jz;  //评价函数值存储;struct pt *p;
};
void main()
{struct pt *we,*we1;int N;cout<<"滑块游戏:";cin>>N;char *a;int b,i;                       //b-数组长度参数，i-数组地址参数;                          char c;a=new char[];                  //输入的字符串;cin>>a;b=strlen(a);                  cout< E > B），耗散值和评价
函数值-----------------pt *wep1,*wep,*we2,*we3;wep1=new pt;wep=wep1;while(we1->p!=NULL){we3=NULL;we=we1;we2=we;while(we->p!=NULL){if(strcmp(we2->a1,we->p->a1)<0){we2=we->p;we3=we;}we=we->p;}(*wep)=(*we2);if(we3!=NULL)we3->p=we2->p;elsewe1=we1->p;wep->p=new pt;wep=wep->p;}(*wep)=(*we1);wep->p=NULL;wep=wep1;while(wep!=NULL){cout<a1<<"              "<hs<<"     "<jz<p;}}
//----------子函数-------------
int evaluation(char *n)     //评价函数;
{int h,m,l;l=0;h=strlen(n);      for(int s=0;s

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！