Puzzle UVA - 227
A children’s puzzle that was popular 30 years ago consisted of a 5×5 frame which contained 24 small
squares of equal size. A unique letter of the alphabet was printed on each small square. Since there
were only 24 squares within the frame, the frame also contained an empty position which was the same
size as a small square. A square could be moved into that empty position if it were immediately to the
right, to the left, above, or below the empty position. The object of the puzzle was to slide squares
into the 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 after
the 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 and
the sequence of moves on the puzzle. The first 5 lines of each puzzle description are the starting
configuration. 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 other
lines follow in order. The empty position in a frame is indicated by a blank. Each display line contains
exactly 5 characters, beginning with the character on the leftmost square (or a blank if the leftmost
square 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 square
moves into the empty position. A denotes that the square above the empty position moves; B denotes
that the square below the empty position moves; L denotes that the square to the left of the empty
position moves; R denotes that the square to the right of the empty position moves. It is possible that
there is an illegal move, even when it is represented by one of the 4 move characters. If an illegal move
occurs, the puzzle is considered to have no final configuration. This sequence of moves may be spread
over 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.). If
the puzzle has no final configuration, then a message to that effect should follow. Otherwise that final
configuration should be displayed.
Format each line for a final configuration so that there is a single blank character between two
adjacent letters. Treat the empty square the same as a letter. For example, if the blank is an interior
position, 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.
Sample Input
TRGSJ
XDOKI
M VLN
WPABE
UQHCF
ARRBBL0
ABCDE
FGHIJ
KLMNO
PQRS
TUVWX
AAA
LLLL0
ABCDE
FGHIJ
KLMNO
PQRS
TUVWX
AAAAABBRRRLL0
Z
Sample Output
Puzzle #1:
T R G S J
X O K L I
M D V B N
W P A E
U Q H C F
Puzzle #2:
A B C D
F G H I E
K L M N J
P Q R S O
T U V W X
Puzzle #3:
This puzzle has no final configuration.
//总的来说，输入，模拟，体现分而治之，不要多任务并行，和学习一样。
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
char map[5][7];
char cmd[1005];
int main()
{
int cnt=0;
//总的来说，输入，模拟，体现分而治之，不要多任务并行，和学习一样。
while(gets(map[0])){//任务1：为'Z'，完全结束
if(map[0][0]=='Z')return 0;
for(int i=1;i<5;i++){
gets(map[i]);//任务2：读完
}
int xx,yy;//任务3：确定空格（不要边读入边确定）
for(int i=0;i<5;i++)
for(int j=0;j<5;j++){
if(map[i][j]==' '){//只是pdf里行末空格消失了。。实际上是有的
xx=i;
yy=j;
break;
}
}
int k=0;//任务4：读入命令（不要边执行。这样子错了也已经读完了后面的了）
while(cin>>cmd[k]){//知识：cin以'\n','\t',' ' 为分隔，故不读如'\n'
if(cmd[k]=='0')break;
else k++;
}
cmd[k]=0;
getchar();//知识点：gets也会吸'\n'作为结束
int x,y; //技巧：分身术，具有暂存对判断之便，又有不悔棋之便
int flag=0;//合法0
for(int i=0;cmd[i];i++)//任务5：对每一个命令改变棋盘，改变前判断异常
{//小任务1：暂存新位置 (技巧：个数比较少时，还是if else容易写也不慢。。）
switch (cmd[i]){
case 'A':
x=xx-1;
y=yy;
break;
case 'B':
x=xx+1;
y=yy;
break;
case 'L':
x=xx;
y=yy-1;
break;
case 'R':
x=xx;
y=yy+1;
break;
default:
flag=1; //只是容错，题中其实已经说了命令只有4个符号
}
if(x<0||x>4||y<0||y>4){//小任务2：判断合理性
flag=1;
}
if(flag)break;//小心写flag=1了！=不是判断符
else{
map[xx][yy]=map[x][y];//小任务3：交换
map[x][y]=' ';//技巧：想想就是' '，其实交换简单
xx=x;yy=y;//记得改变空格位置！
}
}
//任务6：输出
//小任务1：技巧：控制换行,妙
if(cnt++)putchar('\n');
//小任务2：输出公共部分
printf("Puzzle #%d:\n",cnt);
if(flag){//小任务3：解决简单的不合理
printf("This puzzle has no final configuration.\n");
}else{//小任务4：解决输出
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
if(j)putchar(' ');//技巧：解决空格，妙
printf("%c",map[i][j]);
}
putchar('\n');
}
}
}
return 0;
}