1567: 折纸
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 10 Solved: 3
[Submit][Status][Web Board]
Description
小
熊vee很喜欢玩折纸，所以经常把她哥哥的作业本撕下来折纸，今天vee纸张的时候突然想到了一个问题，给你一张格子张纸（....
就是小学时写作业用的小字本一样的格子）共有n行，m列，然后规定你有四种折的方法，top flip，bottom flip，left
flip，right flip。
top flip： 是将最上面的第一行翻折，并与第二行重叠，在第二行之上。（于是折之前的第二行将变为第一行）
bottom flip：是指将最下面的一行翻折，并与倒数第二行重叠，在倒数第二行之上。
left flip： 是指将最左边的一列翻折，并与从左数第二列重叠。
right flip： 是指将最右边的一列翻折，并与从右数第二列重叠。
翻折都是向上翻。当然，经过n+m-2次规定的顺序折叠之后，纸张就重叠在同一个小方格上去了。
现在vee想知道在折纸后，从底端到顶端，每个小格子都是对应着原先的哪个位置。
Input
有 多组数据，每次第一行输入两个整数n m（1<=n，m<=20）。第二行输入个 n+m-2长的字符串来表示折叠的顺序，由四个字母组成：'T','B','L','R'.分别表示top flip，bottom flip，left flip，right flip。n，m等于0是结束程序。
Output
对于每组数据，先输出“case :t”t表示第几组数据，接下来输出n*m行，每行输出两个数 r，c。表示折叠之后从底端到顶端分别对应的着原先的位置。 都从1开始。
Sample Input
2 3
LRT
1 1
2 2
LB
0 0
Sample Output
case 1:
2 2
2 1
2 3
1 3
1 1
1 2
case 2:
1 1
case 3:
1 2
1 1
2 1
2 2
纯模拟题啊，通过小涛神的指点，用二维的栈来模拟折叠的过程，给定四个边界值，每次折叠后改变一次边界值，现假设要将某点向下折叠，那么就将这个栈的元素加入下行加1的栈中...... 注意最后要求是将底部的先输出。
代码如下：
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
struct P
{
int x, y;
} temp;
stack< P >s[25][25];
int t, b, l, r;
void T()
{
for( int i= l; i<= r; ++i )
{
while( !s[t][i].empty() )
{
temp= s[t][i].top();
s[t][i].pop();
s[t+ 1][i].push( temp );
}
}
}
void B()
{
for( int i= l; i<= r; ++i )
{
while( !s[b][i].empty() )
{
temp= s[b][i].top();
s[b][i].pop();
s[b- 1][i].push( temp );
}
}
}
void L()
{
for( int i= t; i<= b; ++i )
{
while( !s[i][l].empty() )
{
temp= s[i][l].top();
s[i][l].pop();
s[i][l+ 1].push( temp );
}
}
}
void R()
{
for( int i= t; i<= b; ++i )
{
while( !s[i][r].empty() )
{
temp= s[i][r].top();
s[i][r].pop();
s[i][r- 1].push( temp );
}
}
}
int main()
{
int N, M, ca= 1;
while( scanf( "%d %d", &N, &M ), N| M )
{
printf( "case %d:\n", ca++ );
if( N+ M- 2== 0 )
{
printf( "1 1\n" );
continue;
}
stack< P > res;
t= 1, b= N, l= 1, r= M;
for( int i= 1; i<= N; ++i )
{
for( int j= 1; j<= M; ++j )
{
temp.x= i, temp.y= j;
s[i][j].push( temp );
}
}
char op[100], len;
scanf( "%s", op );
len= strlen( op );
for( int i= 0; i< len; ++i )
{
switch( op[i] )
{
case 'T':
{
T();
t++;
break;
}
case 'B':
{
B();
b--;
break;
}
case 'L':
{
L();
l++;
break;
}
case 'R':
{
R();
r--;
break;
}
}
}
while( !s[t][l].empty() )
{
temp= s[t][l].top();
s[t][l].pop();
res.push( temp );
}
while( !res.empty() )
{
temp= res.top();
res.pop();
printf( "%d %d\n", temp.x, temp.y );
}
}
}