网络赛前10奖励计蒜客的本子或鼠标垫(外校也可以来现场领取)

问题 1001. -- 又是苹果

1001: 又是苹果

时间限制: 1 Sec  内存限制: 128 MB
提交: 712  解决: 97
[提交][状态][讨论版]

题目描述

最近,亮亮和小W都对苹果很感兴趣!在研究了“最大苹果矩阵”和“给苹果树施肥”的问题后,他们又遇到了一个新的问题:

有一块长n米、宽m米的地,现在小W把地划分成边长1米的小正方形块,共n*m个块。每个块中可能种有一棵苹果树,或放有一个iPhone,也可以什么也没有。然而,亮亮拥有一种超能力,可以将2个宽1米、长度相同的矩形块在空间中直接交换。

亮亮经常对着农场施展超能力,为了不把自己搞晕,他每次总是选择两整行(长度均为m米)或两整列(长度均为n米)进行交换。小W对此十分恼火——当他想拿iPhone打游戏时,却莫名其妙地撞在了苹果树上。小W要求你写一个程序,帮助他确定某一正方形块中放了什么东西。

输入

输入包含多组数据,请处理到文件结束。
每组数据,第一行2个整数n、m,表示地的尺寸。
之后n行,每行m个英文字母,大写的T表示这里种有苹果树,小写的i表示这里放有iPhone,其他字符表示这里什么也没有。
之后1行,一个整数Q,表示小W询问的次数。
之后Q行,包含3个整数,可能有以下情况:
    1 i1 j1 表示小W想知道第i1行第j1列的方块中有什么东西。
    2 i1 i2 表示亮亮交换了第i1行与第i2行。
    3 j1 j2 表示亮亮交换了第j1列与第j2列。
对于100%的数据,有1<=n*m<=106,1<=Q<=105,1<=i1, i2<=n,1<=j1, j2<=m。

输出

对于每组数据,输出以一行“Case #x:”开头,x表示数据的编号,从1开始。
对于小W的每次格式为“1 i j”的询问,输出一行。若方块中是苹果树,输出"Tree"。若方块中是iPhone,输出“Phone”。若方块中什么也没有,输出“Empty”。

样例输入

2 2
Ti
Ti
2
1 1 1
1 2 2
3 3
Tct
Iai
qqT
3
1 1 3
2 1 2
1 1 3

样例输出

Case #1:
Tree
Phone
Case #2:
Empty
Phone

提示

输入数据只保证n*m在106以内,也就是说n和m都可能高达106。直接开106*106的数组肯定会MLE,请自行管理内存。

来源

[提交][状态][讨论版]