题目
查看提交统计提问
总时间限制: 15000ms 内存限制: 150000kB
描述
The rotation game uses a # shaped board, which can hold 24 pieces of square blocks (see Fig.1). The blocks are marked with symbols 1, 2 and 3, with exactly 8 pieces of each kind.
Initially, the blocks are placed on the board randomly. Your task is to move the blocks so that the eight blocks placed in the center square have the same symbol marked. There is only one type of valid move, which is to rotate one of the four lines, each consisting of seven blocks. That is, six blocks in the line are moved towards the head by one block and the head block is moved to the end of the line. The eight possible moves are marked with capital letters A to H. Figure 1 illustrates two consecutive moves, move A and move C from some initial configuration.
输入
The input consists of no more than 30 test cases. Each test case has only one line that contains 24 numbers, which are the symbols of the blocks in the initial configuration. The rows of blocks are listed from top to bottom. For each row the blocks are listed from left to right. The numbers are separated by spaces. For example, the first test case in the sample input corresponds to the initial configuration in Fig.1. There are no blank lines between cases. There is a line containing a single 0' after the last test case that ends the input. 输出 For each test case, you must output two lines. The first line contains all the moves needed to reach the final configuration. Each move is a letter, ranging from A’ to H', and there should not be any spaces between the letters in the line. If no moves are needed, output No moves needed’ instead. In the second line, you must output the symbol of the blocks in the center square after these moves. If there are several possible solutions, you must output the one that uses the least number of moves. If there is still more than one possible solution, you must output the solution that is smallest in dictionary order for the letters of the moves. There is no need to output blank lines between cases.
样例输入
1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0
样例输出
AC
2
DDHH
2
翻译
题目：旋转游戏
描述:
旋转游戏使用一个#形板，可以容纳24块方块（见图1）。这些块用符号1、2和3标记，每种都有8块。
最初，这些块被随机放置在板上。您的任务是移动这些块，以便放置在中心正方形中的八个块具有相同的标记符号。
只有一种有效的移动方式，即旋转四条线中的一条，每条线由七个块组成。
也就是说，行中的六个块向头部移动一个块，头部块移动到行的末尾。
八种可能的移动用大写字母A到H标记。图1显示了从初始配置开始的两个连续移动，移动A和移动C。
输入：
输入由不超过30个测试用例组成。每个测试用例只有一行包含24个数字，这些数字是初始配置中块的符号。
块的行是从上到下列出的。对于每一行，块从左到右列出。这些数字用空格隔开。
例如，样本输入中的第一个测试用例对应于图1中的初始配置。案例之间没有空白行。
在结束输入的最后一个测试用例之后，有一行包含一个“0”。
输出：
对于每个测试用例，您必须输出两行。第一行包含达到最终配置所需的所有操作。
每个移动都是一个字母，从“a”到“H”，行中的字母之间不应有任何空格。
如果不需要移动，则输出“不需要移动”。在第二行中，您必须在这些移动后输出中心正方形中块的符号。
如果有几个可能的解决方案，则必须输出使用最少移动次数的解决方案。
如果仍然有多个可能的解决方案，则必须输出移动字母的字典顺序中最小的解决方案。
不需要在案例之间输出空行。
代码
#include <bits/stdc++.h>
using namespace std;
const int h[8]={0,0,0,1,0,1,0,0};//属于模仿的行
const int l[8]={0,0,0,1,0,1,0,0};//属于模仿的列
const int oppsite[9]={0,6,5,8,7,2,1,4,3};//相反操作
int limit=0,//搜索深度，在该范围中找最短距离
op[100];//记住操作过程
struct board{
int d[8][8];
bool ok(){//判断是否拼接成功
int f=0;
for(int i=3;i<=5;i++)for(int j=3;j<=5;j++){
if(i= =4&&j= =4)continue;
if(!f)f=d[i][j];
else if(f!=d[i][j])return 0;
}
return 1;
}
int how(){//判断还需要操作几步，才能拼接完整
int m[4]={0},maxm=0;
for(int i=3;i<=5;i++)for(int j=3;j<=5;j++)
if(!(i= =4&&j= =4))m[d[i][j]]++;
maxm=max(m[1],max(m[2],m[3]));//1、2、3块的最多数
return 8-maxm;//共8块，需要凑几个
}
void change(int x){//1-8表示四条线八个方向的移动
int dx;
switch(x){
case 1://a左竖线往上
dx=d[1][3];
for(int i=1;i<7;i++)d[i][3]=d[i+1][3];
d[7][3]=dx;
break;
case 2://b右竖线往上
dx=d[1][5];
for(int i=1;i<7;i++)d[i][5]=d[i+1][5];
d[7][5]=dx;
break;
case 3://c上横线往右
dx=d[3][7];
for(int i=7;i>1;i–)d[3][i]=d[3][i-1];
d[3][1]=dx;
break;
case 4://d下横线往右
dx=d[5][7];
for(int i=7;i>1;i–)d[5][i]=d[5][i-1];
d[5][1]=dx;
break;
break;
case 5://右竖线往下
dx=d[7][5];
for(int i=7;i>1;i–)d[i][5]=d[i-1][5];
d[1][5]=dx;
break;
case 6://左竖线往下
dx=d[7][3];
for(int i=7;i>1;i–)d[i][3]=d[i-1][3];
d[1][3]=dx;
break;
case 7://下横线往左
dx=d[5][1];
for(int i=1;i<7;i++)d[5][i]=d[5][i+1];
d[5][7]=dx;
break;
case 8://上横线往左
dx=d[3][1];
for(int i=1;i<7;i++)d[3][i]=d[3][i+1];
d[3][7]=dx;
break;
}
}
void view(string s){
cout<<s<<endl;
for(int i=1;i<=7;i++){
for(int j=1;j<=7;j++)
if(h[i]||l[j])cout<<d[i][j]<<" “;
else cout<<” “;
cout<<endl;
}
}
}b;
bool go(int x,int step){//递归深搜，枚举所有操作。两参数，上步操作和操作次数
//本次不能是上次的逆操作，形成反复拉锯
if(b.how()+step>limit)return 0; //递归出口：需要步数+已操作步数不能超过限定范围
//b.how()是拼接面需要拼接几个数字，step是已经完成步数
//cout<<“差距：”<<b.how()<<”+“<<step<<“步数\t范围<=”<<limit<<endl;;
if(b.ok()){
//cout<<”-----------------------------------------\n";
return 1;}
//cout<<“循环\n”;
for(int i=1;i<=8;i++){
//cout<<“操作”<<i<<endl;
if(oppsite[x]= =i)continue;//不做相反拉锯操作
op[step]=i;
b.change(i);
//b.view(“变化”);
if(go(i,step+1))return 1;
b.change(oppsite[i]);//回溯，恢复
//b.view(“恢复”);
}
return 0;
}
int main(){
//freopen(“data.cpp”,“r”,stdin);
int d;
while(1){//循环到输入0
for(int i=1;i<=7;i++)//7行
for(int j=1;j<=7;j++)//7列
if(h[i]||l[j]){//到魔方行列才输入值
cin>>d;
b.d[i][j]=d;
if(d==0)return 0;//输入0退出程序
}else b.d[i][j]=0;
//b.view(“开始”);
limit=0;//a*算法的估计代价，现在是在该范围内求解
while(!go(0,0)){//在limit范围内递归深搜，枚举所有操作
//cout<<“范围：”<<limit<<endl;
limit++;//本次无解，就扩展范围
}
//b.view(“结果”);
if(limit= =0)cout<<“No moves needed”;//不用移动达目标
//cout<<“ok\n”;
for(int i=0;i<limit;i++)cout<<char(‘A’+op[i]-1);cout<<endl;//顺次输出最短操作
cout<<b.d[3][3]<<endl;//模仿拼接面数字
}
return 0;
}
理解
宽搜——点和点距离没有代价
迪杰斯特拉算法——宽搜升级，最短路径，点和点距离有代价，要计算比较，比较a出发到c、d和b出发到c、d的距离，留下更短的。就是从留下a+c和b+c的更小的。
a算法不仅算a+c，还要算a+t(到终极目标距离)
a是逐步扩展最小代价，直到达到目标。
这其实就是人工智能的一种算法。人工智能和程序设计不是割裂开的，人工智能是程序设计的一部分。
本题就是a算法，总之就是宽搜。把方法讲给，设定约束，让机器人自己走迷宫。程序结构是递归，思路是宽搜，实质上就是枚举（一个个试），a*其实就是剪枝的一种思路。
说的鲁莽了，请批评指正！