题目

问题 B: 华容道(huarong)

题目描述

小童是一个喜欢数字华容道的女生。
数字华容道游戏是一种最早的滑块类游戏，常见的类型有十五数字推盘游戏和八数字推盘游戏等。十五数字华容道游戏的板上会有十五个方块和一个大小相当于一个方块的空位（供方块移动之用）。而八数字华容道游戏，为九宫格布局，有八个方块和一个空位（如图1）。

在小童十岁生日的当天，小童的叔叔送给了她一块八数字华容道游戏作为生日礼物。
在送给小童之前，叔叔打乱了这块华容道，想要小童还原它。
聪明的小童当然立刻就还原了，并且还记下了还原的过程。
第二天上学的时候，小童告诉了你她还原的过程，想要学习信息学竞赛的你编写一个程序回答她，叔叔送她的华容道在小童开始还原之前是什么样的。
具体的，小童还原一共有 n 步，每一步可以用一个字符表示：
第i个字符如果是‘L’，则表示小童第i次是把空位左边的块移到了空位；
第i个字符如果是‘R’，则表示小童第i次是把空位右边的块移到了空位；
第i个字符如果是‘U’，则表示小童第i次是把空位上边的块移到了空位；
第i个字符如果是‘D’，则表示小童第i次是把空位下边的块移到了空位。
另外，小童是一个诚实的孩子，所以她告诉你的还原过程一定是合法的。

输入

第一行一个整数n，表示小童整个还原过程共 n 步。
第二行为一个长度为n的字符串S，第i个字符表示了小童第i步是怎么操作的。

输出

三行三个整数，每行两个整数之间有一个空格，表示华容道一开始的样子，空位的位置用0填充。

样例输入

1
2

4
LURD

样例输出

1
2
3

1 2 3
4 8 5
7 6 0

提示

我们可以通过小童的操作从后往前一步一步倒推出华容道一开始的样子，比如小童第i次操作是把空位下的块往上移倒过来倒推回去就相当于是空位往上移动了一格，然后原本在空位上面的格子里的数往下移。具体对于样例来说就是：
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
4 5 6 -> 4 5 0 -> 4 0 5 -> 4 8 5 -> 4 8 5
7 8 0 7 8 6 7 8 6 7 0 6 7 6 0

【数据范围约定】

对于10% 的数据，n=0；
对于30% 的数据，n≤1；
另有30% 的数据，S中只含有‘L’和‘R’两种字符；
对于所有数据，0≤n≤50，S中只含有‘L’、‘R’、‘U’和‘D’四种字符。

题解

嗯，很好，模拟题，轻轻松松AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include<bits/stdc++.h>
using namespace std;
int n,g[5][5];
char s[55];
int main(){
    g[1][1] = 1; 
    g[1][2] = 2;
    g[1][3] = 3;
    g[2][1] = 4; 
    g[2][2] = 5; 
    g[2][3] = 6;
    g[3][1] = 7; 
    g[3][2] = 8; 
    g[3][3] = 0;
    scanf("%d",&n);
    scanf("%s",s+1);
    int x = 3,y = 3;
    for(int i = n; i >= 1; i--){
        if(s[i] == 'L'){
            swap(g[x][y],g[x][y+1]), y++;
        } else if(s[i] == 'R'){
            swap(g[x][y],g[x][y-1]),y--;
        } else if(s[i] == 'U'){
            swap(g[x][y],g[x+1][y]),x++;
        } else{
            swap(g[x][y],g[x-1][y]),x--;
        }
    }
    for(int i = 1; i <= 3; i++){
         
        for(int j = 1; j < 3; j++)
            printf("%d ",g[i][j]);
        printf("%d\n",g[i][3]);
    }
    return 0;
}