程序设计算法竞赛基础——练习3解题报告
1001 A strange lift
Problem Description
There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button “UP” , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button “DOWN” , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can’t go up high than N,and can’t go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button “UP”, and you’ll go up to the 4 th floor,and if you press the button “DOWN”, the lift can’t do it, because it can’t go down to the -2 th floor,as you know ,the -2 th floor isn’t exist.
Here comes the problem: when you are on floor A,and you want to go to floor B,how many times at least he has to press the button “UP” or “DOWN”?
Input
The input consists of several test cases.,Each test case contains two lines.
The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,…kn.
A single 0 indicate the end of the input.
Output
For each case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can’t reach floor B,printf “-1”.
Sample Input
5 1 5
3 3 1 2 5
0
Sample Output
3
解题思路
电梯上升不能超过最高层，下降不能低于1楼，每楼最多只能前往一次以保证最优解
代码实现
#include<iostream>
using namespace std;
const int maxn = 1e6 + 5;
//fl表示该层按钮情况 time存放到达该层所需最小次数
struct INF {
int fl;
int time;
};
INF flor[205];
int n;
void search(const int a, const int b) {
if(a != b) {
int up = flor[a].fl + a;
int down = a - flor[a].fl;
int newtime = flor[a].time + 1;
//上升层存在且第一次到达
if(newtime < flor[up].time && up <= n) {
flor[up].time = newtime;
search(up, b);
}
//下降层存在且第一次到达
if(newtime < flor[down].time && down >= 1) {
flor[down].time = newtime;
search(down, b);
}
}
}
int main() {
int a, b;
while(cin >> n && n != 0) {
cin >> a >> b;
for(int i = 1; i <= n; i++) {
cin >> flor[i].fl;
flor[i].time = maxn;
}
flor[a].time = 0;
search(a, b);
if(flor[b].time == maxn) cout << -1 << endl;
else cout << flor[b].time << endl;
}
return 0;
}
1002 A计划
Problem Description
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。
Input
输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小NM（1 <= N,M <=10)。T如上所意。接下去的前NM表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。
Output
如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。
Sample Input
1
5 5 14
S*#*.
.#...
.....
****.
...#.
..*.P
#.*..
***..
...*.
*.#..
Sample Output
YES
Source
HDU 2007-6 Programming Contest
解题思路
用一个三维数组fl2 [12] **[12]**储存迷宫地图，**fl[0] [ ] [ ]**存放第一层迷宫地图， **fl1 [ ] [ ]**存放第二层迷宫地图
每次经过一个点就将该点变成墙，保证每次到达某个点都是最优情况
如果传送门对面也是传送门或是墙则不能使用该传送门
代码实现
#include<queue>
#include<iostream>
using namespace std;
//kase为迷宫地面状况，times表示到达该点所用时间，x,y,z存放改格迷宫所在位置（为que队列服务）
struct INF {
char kase;
int times;
int x, y, z;
};
//用于读入迷宫地图，防止读入空格换行等
char mygetchar() {
char ch;
while(true) {
cin >> ch;
if(ch == 'S' || ch == '*' || ch == '.' || ch == 'P' || ch == '#') return ch;
}
}
//清空队列
void clearqueue(queue<INF>& q) {
queue<INF> empty;
swap(empty, q);
}
INF fl[2][12][12];
queue<INF> que;
int main() {
int c;
cin >> c;
while(c--) {
clearqueue(que);
int n, m, t;
//havefound表示是否已经找到公主
bool havefound = false;
cin >> n >> m >> t;
for(int i = 0; i < 2; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < m; k++) {
fl[i][j][k].kase = mygetchar();
fl[i][j][k].x = i;
fl[i][j][k].y = j;
fl[i][j][k].z = k;
}
}
}
//从入口fl[0][0][0]出发开始寻找
fl[0][0][0].times = 0;
que.push(fl[0][0][0]);
fl[0][0][0].kase = '*';
while(!que.empty()) {
INF temp = que.front();
que.pop();
//改格为入口S或者平路.
if(temp.kase == '.' || temp.kase == 'S') {
//右边没越界且无墙
if(temp.z + 1 < m && fl[temp.x][temp.y][temp.z + 1].kase != '*') {
fl[temp.x][temp.y][temp.z + 1].times = temp.times + 1;
que.push(fl[temp.x][temp.y][temp.z + 1]);
fl[temp.x][temp.y][temp.z + 1].kase = '*';
}
//左边没越界且无墙
if(temp.z - 1 >= 0 && fl[temp.x][temp.y][temp.z - 1].kase != '*') {
fl[temp.x][temp.y][temp.z - 1].times = temp.times + 1;
que.push(fl[temp.x][temp.y][temp.z - 1]);
fl[temp.x][temp.y][temp.z - 1].kase = '*';
}
//下面没越界且无墙
if(temp.y + 1 < n && fl[temp.x][temp.y + 1][temp.z].kase != '*') {
fl[temp.x][temp.y + 1][temp.z].times = temp.times + 1;
que.push(fl[temp.x][temp.y + 1][temp.z]);
fl[temp.x][temp.y + 1][temp.z].kase = '*';
}
//上面没越界且无墙
if(temp.y - 1 >= 0 && fl[temp.x][temp.y - 1][temp.z].kase != '*') {
fl[temp.x][temp.y - 1][temp.z].times = temp.times + 1;
que.push(fl[temp.x][temp.y - 1][temp.z]);
fl[temp.x][temp.y - 1][temp.z].kase = '*';
}
}
//改格为传送门
else if(temp.kase == '#') {
int newx = (temp.x + 1) % 2;
//传送门对面无墙且不是传送门
if(fl[newx][temp.y][temp.z].kase != '*' && fl[newx][temp.y][temp.z].kase != '#') {
fl[newx][temp.y][temp.z].times = temp.times;
que.push(fl[newx][temp.y][temp.z]);
fl[newx][temp.y][temp.z].kase = '*';
}
}
//在规定时间内找到公主位置
else if(temp.kase == 'P' && temp.times <= t) {
cout << "YES" << endl;
havefound = true;
break;
}
}
if(!havefound) cout << "NO" << endl;
}
return 0;
}
1003 N皇后问题
Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0
Sample Output
1
92
10
Author
cgf
Source
2008 HZNU Programming Contest
解题思路
刚开始做时以为只是皇后所在格子周围八格不能使用，后面才发现是每行每列每条对角线上都只能放一个皇后
代码实现
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int row[12];
bool line[12];
int anwser[12];
int n;
int kase(const int l1, const int kas) {
//kas为已经找到的位置，找到n个位置说明该方案可行
if(kas == n) return 1;
//从第一行第一个位置开始向右寻找，sum存放已经找到kas个位置后找剩余位置时还有多少种可能
int sum = 0;
int i = l1 + 1;
for(int j = 1 ; j <= n; j++) {
//格子所在列必须是没有使用的才能选择
if(!line[j]) {
//able继续讨论该格子能不能满足要求，不能满足要求时直接跳出
bool able = true;
//对角线不能被使用过
int tk = i - 1, t1 = j - 1, t2 = j + 1;
while(tk > 0){
if((t1 > 0 && row[tk] == t1) || (t2 <= n && row[tk] == t2)) {
able = false;
break;
}
tk--;
t1--;
t2++;
}
//格子满足所有要求，可以使用
if(able) {
//使用该格子
row[i] = j;
//line[j]变为不可用，下一行
line[j] = true;
//寻找使用该格子后能得到几种可行方案
sum += kase(i, kas + 1);
//将tab恢复为使用该格子前的状态
line[j] = false;
row[i] = 0;
}
}
}
return sum;
}
int main() {
for(n = 1 ; n <= 10; n++) anwser[n] = kase(0,0);
while(cin >> n && n != 0) {
cout << anwser[n] << endl;
}
return 0;
}
1004 Sudoku Killer
Problem Description
自从2006年3月10日至11日的首届数独世界锦标赛以后，数独这项游戏越来越受到人们的喜爱和重视。
据说，在2008北京奥运会上，会将数独列为一个单独的项目进行比赛，冠军将有可能获得的一份巨大的奖品———HDU免费七日游外加lcy亲笔签名以及同hdu acm team合影留念的机会。
所以全球人民前仆后继，为了奖品日夜训练茶饭不思。当然也包括初学者linle，不过他太笨了又没有多少耐性，只能做做最最基本的数独题，不过他还是想得到那些奖品，你能帮帮他吗？你只要把答案告诉他就可以，不用教他是怎么做的。
数独游戏的规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3x3的方格都包含1-9这九个数字。
例题：
答案：
Input
本题包含多组测试，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。
Output
对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。
对于每组测试数据保证它有且只有一个解。
Sample Input
7 1 2 ? 6 ? 3 5 8
? 6 5 2 ? 7 1 ? 4
? ? 8 5 1 3 6 7 2
9 2 4 ? 5 6 ? 3 7
5 ? 6 ? ? ? 2 4 1
1 ? 3 7 2 ? 9 ? 5
? ? 1 9 7 5 4 8 6
6 ? 7 8 3 ? 5 1 9
8 5 9 ? 4 ? ? 2 3
Sample Output
7 1 2 4 6 9 3 5 8
3 6 5 2 8 7 1 9 4
4 9 8 5 1 3 6 7 2
9 2 4 1 5 6 8 3 7
5 7 6 3 9 8 2 4 1
1 8 3 7 2 4 9 6 5
2 3 1 9 7 5 4 8 6
6 4 7 8 3 2 5 1 9
8 5 9 6 4 1 7 2 3
Author
linle
Source
ACM暑期集训队练习赛（三）
解题思路
可填入数字不能是已经在？所在行丶所在列丶所在小矩阵出现过的数字
代码实现
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
//arr[9][9]存放矩阵信息，ask[90]存放“？”所在位置
char arr[9][9];
int ask[90];
int tas;
//判断数字t是否在？所在行丶所在列丶所在小矩阵已经使用过
bool vis(const int x, const int y, const int t) {
for(int i = 0; i < 9; i++) {
if(arr[x][i] - '0' == t) return false;
if(arr[i][y] - '0' == t) return false;
}
for(int i = x / 3 * 3; i < x / 3 * 3 + 3; i++) {
for(int j = y / 3 * 3; j < y / 3 * 3 + 3; j++) {
if(arr[i][j] - '0' == t) return false;
}
}
return true;
}
bool DFS(const int kase) {
if(tas == kase) return true;
int x = ask[kase] / 9, y = ask[kase] % 9;
for(int i = 1; i <= 9; i++) {
if(vis(x, y, i)) {
arr[x][y] = i + '0';
if(DFS(kase + 1)) return true;
arr[x][y] = '?';
}
}
return false;
}
int main() {
//firstkase表示是否为第一组数据，当不为第一组数据时需要多输出一个\n
bool firstkase = true;
while(scanf(" %c", &arr[0][0]) != EOF) {
tas = 0;
if(arr[0][0] == '?') ask[tas++] = 0;
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(i == 0 && j == 0) continue;
scanf(" %c", &arr[i][j]);
if(arr[i][j] == '?') ask[tas++] = i * 9 + j;
}
}
DFS(0);
if(firstkase) firstkase = false;
else cout << endl;
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 8; j++) {
printf("%c ", arr[i][j]);
}
printf("%c\n", arr[i][8]);
}
}
return 0;
}
1005 Oil Deposits
Problem Description
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either *', representing the absence of oil, or@’, representing an oil pocket.
Output
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
Sample Input
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output
0
1
2
2
Source
Mid-Central USA 1997
解题思路
如果一个@出现在其他@的上下左右，左上，右上，左下，右下，则认为这两个@属于同一块油田
从第一个@开始寻找，找完和其连接的所有@再开始寻找下一块油田
代码实现
#include<iostream>
#include<queue>
using namespace std;
struct INF {
int L1, L2;
};
//oil为true表示@，false表示*
bool oil[105][105];
queue<INF> que;
int main() {
int m, n;
while(cin >> m >> n && m != 0) {
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
while(true) {
char ch;
cin >> ch;
if(ch == '*') {
oil[i][j] = false;
break;
} else if(ch == '@') {
oil[i][j] = true;
break;
}
}
}
}
int sum = 0;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(oil[i][j]) {
sum++;
INF temp;
temp.L1 = i;
temp.L2 = j;
que.push(temp);
oil[i][j] = false;
while(!que.empty()) {
INF te = que.front();
que.pop();
//右
if(te.L2 + 1 <= n && oil[te.L1][te.L2 + 1]) {
INF right;
right.L1 = te.L1;
right.L2 = te.L2 + 1;
que.push(right);
oil[right.L1][right.L2] = false;
}
//左
if(te.L2 - 1 > 0 && oil[te.L1][te.L2 - 1]) {
INF left;
left.L1 = te.L1;
left.L2 = te.L2 - 1;
que.push(left);
oil[left.L1][left.L2] = false;
}
//上
if(te.L1 - 1 > 0 && oil[te.L1 - 1][te.L2]) {
INF up;
up.L1 = te.L1 - 1;
up.L2 = te.L2;
que.push(up);
oil[up.L1][up.L2] = false;
}
//下
if(te.L1 + 1 <= m && oil[te.L1 + 1][te.L2]) {
INF down;
down.L1 = te.L1 + 1;
down.L2 = te.L2;
que.push(down);
oil[down.L1][down.L2] = false;
}
//左上
if(te.L1 - 1 > 0 && te.L2 - 1 > 0 && oil[te.L1 - 1][te.L2 - 1]) {
INF leup;
leup.L1 = te.L1 - 1;
leup.L2 = te.L2 - 1;
que.push(leup);
oil[leup.L1][leup.L2] = false;
}
//右上
if(te.L1 - 1 > 0 && te.L2 + 1 <= n && oil[te.L1 - 1][te.L2 + 1]) {
INF rigup;
rigup.L1 = te.L1 - 1;
rigup.L2 = te.L2 + 1;
que.push(rigup);
oil[rigup.L1][rigup.L2] = false;
}
//左下
if(te.L1 + 1 <= m && te.L2 - 1 > 0 && oil[te.L1 + 1][te.L2 - 1]) {
INF ledown;
ledown.L1 = te.L1 + 1;
ledown.L2 = te.L2 - 1;
que.push(ledown);
oil[ledown.L1][ledown.L2] = false;
}
//右上
if(te.L1 + 1 <= m && te.L2 + 1 <= n && oil[te.L1 + 1][te.L2 + 1]) {
INF rigdown;
rigdown.L1 = te.L1 + 1;
rigdown.L2 = te.L2 + 1;
que.push(rigdown);
oil[rigdown.L1][rigdown.L2] = false;
}
}
}
}
}
cout << sum << endl;
}
return 0;
}
1006 The Rotation Game
Problem Description
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.
Input
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.
Output
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' toH’, 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.
Sample Input
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
Sample Output
AC
2
DDHH
2
Source
2004 Asia Regional Shanghai
解题思路
题目实现其实并不难，只是缺少思路，我也是借鉴了其他人的思路才得以AC
注意当你上一次使用A时下一次就不能用F
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
int arr[30];
vector<char> step;
//判断中心是否已经达到要求
bool check() {
int temp = arr[7];
return arr[8] == temp && arr[9] == temp && arr[12] == temp && arr[13] == temp && arr[16] == temp && arr[17] == temp && arr[18] == temp;
}
//判断中心至少还需要几次移动，即8减去中心出现最多数的次数
int need() {
int t[4];
t[1] = t[2] = t[3] = 0;
t[arr[7]]++;
t[arr[8]]++;
t[arr[9]]++;
t[arr[12]]++;
t[arr[13]]++;
t[arr[16]]++;
t[arr[17]]++;
t[arr[18]]++;
return 8 - max(t[1],max(t[2], t[3]));
}
//交换（把a1~a7整体前移，a7变成a1）
void swap(const int a1, const int a2, const int a3, const int a4, const int a5, const int a6, const int a7) {
int temp = arr[a1];
arr[a1] = arr[a2];
arr[a2] = arr[a3];
arr[a3] = arr[a4];
arr[a4] = arr[a5];
arr[a5] = arr[a6];
arr[a6] = arr[a7];
arr[a7] = temp;
}
//主要搜索部分 maxdp：最大移动次数 now_dp：已经移动次数 lase_step：上一步移动方法
bool DFS(const int maxdp, const int now_dp, const int last_step) {
//如果 现在已经移动次数+至少还需次数 > 允许最大移动次数 或者已经移动最大移动次数后仍没有找到则返回false
if(now_dp + need() > maxdp || now_dp == maxdp) return false;
//按照ABCDEFGH的顺序判断
if(last_step != 6) {
swap(1, 3, 7, 12, 16, 21, 23);
step.push_back('A');
if(check()) return true;
if(DFS(maxdp, now_dp + 1, 1)) return true;
step.pop_back();
swap(23, 21, 16, 12, 7, 3, 1);
}
if(last_step != 5) {
swap(2, 4, 9, 13, 18, 22, 24);
step.push_back('B');
if(check()) return true;
if(DFS(maxdp, now_dp + 1, 2)) return true;
step.pop_back();
swap(24, 22, 18, 13, 9, 4, 2);
}
if(last_step != 8) {
swap(11, 10, 9, 8, 7, 6, 5);
step.push_back('C');
if(check()) return true;
if(DFS(maxdp, now_dp + 1, 3)) return true;
step.pop_back();
swap(5, 6, 7, 8, 9, 10, 11);
}
if(last_step != 7) {
swap(20, 19, 18, 17, 16, 15, 14);
step.push_back('D');
if(check()) return true;
if(DFS(maxdp, now_dp + 1, 4)) return true;
step.pop_back();
swap(14, 15, 16, 17, 18, 19, 20);
}
if(last_step != 2) {
swap(24, 22, 18, 13, 9, 4, 2);
step.push_back('E');
if(check()) return true;
if(DFS(maxdp, now_dp + 1, 5)) return true;
step.pop_back();
swap(2, 4, 9, 13, 18, 22, 24);
}
if(last_step != 1) {
swap(23, 21, 16, 12, 7, 3, 1);
step.push_back('F');
if(check()) return true;
if(DFS(maxdp, now_dp + 1, 6)) return true;
step.pop_back();
swap(1, 3, 7, 12, 16, 21, 23);
}
if(last_step != 4) {
swap(14, 15, 16, 17, 18, 19, 20);
step.push_back('G');
if(check()) return true;
if(DFS(maxdp, now_dp + 1, 7)) return true;
step.pop_back();
swap(20, 19, 18, 17, 16, 15, 14);
}
if(last_step != 3) {
swap(5, 6, 7, 8, 9, 10, 11);
step.push_back('H');
if(check()) return true;
if(DFS(maxdp, now_dp + 1, 8)) return true;
step.pop_back();
swap(11, 10, 9, 8, 7, 6, 5);
}
return false;
}
int main(){
//读入0时结束输入
while(~scanf("%d", &arr[1]) && arr[1] != 0) {
for(int i = 2; i <= 24; i++) {
scanf("%d", &arr[i]);
}
if(check()) {
printf("No moves needed\n%d\n", arr[7]);
continue;
}
//found表示是否已经找到最优解
bool found = false;
for(int dp = 1; !found; dp++) {
step.clear();
if(DFS(dp, 0, 0)) {
found = true;
for(int i = 0; i < step.size(); i++) printf("%c", step[i]);
printf("\n%d\n", arr[8]);
}
}
}
return 0;
}