《算法竞赛入门经典》（第2版） 习题3-5 谜题
题目
习题3-5 谜题（Puzzle，ACM/ICPC World Finals 1993,UVa227）
有一个5*5的网格，其中恰好有一个格子是空的，其他格子各有一个字母。一共有4种指令：A,B,L,R，分别表示把空格上、下、左、右的相邻字母移到空格中。输入初始网格和指令序列（以数字0结束），输出指令执行完毕后的网格。如果有非法指令，应输出“This puzzle has no final configuration.”（哎呀，其实就是移动空格啦）
UVa上的英文原题我粘贴在下面了（UVa的OJ网站网速真的感人，点一下我可以去听完一首情歌王了）：
227 Puzzle
A children’s puzzle that was popular 30 years ago consisted of a 5*5 frame which contained 24 smallsquares of equal size. A unique letter of the alphabet was printed on each small square. Since therewere only 24 squares within the frame, the frame also contained an empty position which was the samesize as a small square. A square could be moved into that empty position if it were immediately to theright, to the left, above, or below the empty position. The object of the puzzle was to slide squares intothe empty position so that the frame displayed the letters in alphabetical order.
The illustration below represents a puzzle in its original configuration and in its configuration afterthe following sequence of 6 moves:
- The square above the empty position moves.
- The square to the right of the empty position moves.
- The square to the right of the empty position moves.
- The square below the empty position moves.
- The square below the empty position moves.
- The square to the left of the empty position moves.
Write a program to display resulting frames given their initial configurations and sequences of moves.
Input
Input for your program consists of several puzzles. Each is described by its initial configuration andthe sequence of moves on the puzzle. The first 5 lines of each puzzle description are the startingconfiguration. Subsequent lines give the sequence of moves.
The first line of the frame display corresponds to the top line of squares in the puzzle. The otherlines follow in order. The empty position in a frame is indicated by a blank. Each display line containsexactly 5 characters, beginning with the character on the leftmost square (or a blank if the leftmostsquare is actually the empty frame position). The display lines will correspond to a legitimate puzzle.
The sequence of moves is represented by a sequence of As, Bs, Rs, and Ls to denote which squaremoves into the empty position. A denotes that the square above the empty position moves; B denotesthat the square below the empty position moves; L denotes that the square to the left of the emptyposition moves; R denotes that the square to the right of the empty position moves. It is possible thatthere is an illegal move, even when it is represented by one of the 4 move characters. If an illegal moveoccurs, the puzzle is considered to have no final configuration. This sequence of moves may be spreadover several lines, but it always ends in the digit 0. The end of data is denoted by the character Z.
Output
Output for each puzzle begins with an appropriately labeled number (Puzzle #1,Puzzle #2, etc.). Ifthe puzzle has no final configuration, then a message to that effect should follow. Otherwise that finalconfiguration should be displayed.
Format each line for a final configuration so that there is a single blank character between twoadjacent letters. Treat the empty square the same as a letter. For example, if the blank is an interiorposition, then it will appear as a sequence of 3 blanks — one to separate it from the square to the left,one for the empty position itself, and one to separate it from the square to the right.
Separate output from different puzzle records by one blank line.
Note:The first record of the sample input corresponds to the puzzle illustrated above.
解题思路
这个英文原题真的是又臭又长，但是主要内容就紫书里的几行描述了，要Accepted的话主要注意一下输入、输出格式就OK了。（去英文原题里找，认真阅读一下就好，it is not big deal）
英文原题input和output中重要的部分我加粗了，有需要的可以参考一下。
主要思路就是：5*5方格的输入（当遇到结束输入的标志“Z”，要跳出循环）、空格的位置记录、空格的合法移动判断、输出。
其实思路不难，就是格式什么的注意一下即可。我花了三个小时左右写代码+调试，但是最后两次就AC咯，第一次是PE错误，输出忘记打空行了。海星海星！！！继续加油！！！嘻嘻！！！
AC代码（Uva的OJ）
#include <iostream>
#include <cstring>
#include <string>
#include <fstream>
using namespace std;
//cin 会忽略空格、回车
//getline输入一整行数据，包括空格
const char direction[] = "ABLR";
int legal_move(char dir,int blank_x,int blank_y) {
bool four_direction = false;
for (int i = 0; direction[i]; i++) {
if (direction[i] == dir)
four_direction = true;
}
if (!four_direction) return 0;
if (dir == 'A') blank_x --;
if (dir == 'B') blank_x ++;
if (dir == 'L') blank_y --;
if (dir == 'R') blank_y ++;
if (blank_x < 0 || blank_x >= 5) return 0;
if (blank_y < 0 || blank_y >= 5) return 0;
return 1; //经过层层筛选，能走到这，那就是合法移动啦！
}
int main() {
// freopen("data_in_2_17.txt","r",stdin);
// freopen("data_out_2_17.txt","w",stdout);
int number = 0;
for(;;) {
number ++;
string ss[5];
int blank[2] = {0,0};
bool over = false; //输入是否结束的布尔标志
//输入5*5网格
char gg;
if (number >= 2) scanf("%c", &gg);//吃回车，否则会影响到getline。那只能第一次输入正确了
for (int i =0; i < 5; i++) {
getline(cin,ss[i]);
if (ss[0] == "Z") { //若第一行输入为“Z”，则结束输入
over = true;
break;
}
}
if (over) {
// cout << "输入结束\n";
break;
}
// cout << "输出测试：\n";
// for (int i =0; i < 5; i++) {
// cout << ss[i] << endl;
// }
// cout << "输出测试结束\n";
//找初始的空格位置
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (ss[i][j] == ' ') {
blank[0] = i;
blank[1] = j;
break;
}
}
}
// cout << "空格坐标：" << blank[0] << "," << blank[1] << endl;
//开始移动
char dir;
bool illegal = false;
while (cin >> dir) {
if (dir == '0') break;
int x = blank[0],y = blank[1];
if (legal_move(dir,blank[0],blank[1])) {
if (dir == 'A') x --;
if (dir == 'B') x ++;
if (dir == 'L') y --;
if (dir == 'R') y ++;
char t = ss[x][y]; //SWAP
ss[x][y] = ss[blank[0]] [blank[1]];
ss[blank[0]] [blank[1]] = t;
blank[0] = x; //移动完更新一下空格的位置
blank[1] = y;
}
else { //若非法移动（越界、不是四个方向的字母）
illegal = true;
}
}
//打印最后的结果 a
if (number > 1) cout << endl; //打空行
if (illegal) {
printf("Puzzle #%d:\n", number);
printf("This puzzle has no final configuration.\n");
}
else {
printf("Puzzle #%d:\n", number);
for (int i = 0; i < 5; i++) {
for (int j =0; j < 5; j++) {
if (j > 0) cout << " ";
cout << ss[i][j];
}
cout << endl;
}
}
}
return 0;
}