#2375. 梦幻折纸
梦幻折纸
梦幻折纸
题目描述
梦幻折纸 【问题背景】 你是一个喜欢幻想的小女孩,特别喜欢追求一些完美的理想的东西——“理 想的圆”,“理想的均等”,“理想的材料”,“理想的最优解”…… 最近,偶然的机会,你迷恋上了折纸。你把自己的作业本扯下来折成了各种各 样的小把戏——小花,小草,小鸟,小兔子,小老鼠……一张又一张,直到作业本 的封面都被你折成了纸鹤。但是你还是觉得不过瘾。 终于……你克制不住自己心中压抑的想法,从可怜的同桌那儿拿了一张用过 的草稿纸。正当你打算用同样的方法折掉它的时候,你十分惊奇的发现:这不是 一张普通的草稿纸,而是一张非常特殊的草稿纸:它薄得厚度可以忽略不计,柔 韧得怎么撕也撕不破,而且无论怎么折都行。 你如获至宝,这不就是你梦寐以求的“理想的材料”吗?真所谓“踏破铁鞋 无觅处,得来全不费功夫。梦里寻它千百度,蓦然回首,它却在灯火阑珊处 !” 你决心要把它折成一个有难度一点的东西,才对得住一张这么好的纸。 【问题描述】 你仔细观察了一下纸的特点: 纸的大小为n(cm)×m(cm),上面等距离的印好了格线,n-1 条横线和m-1 条竖 线(线的宽度忽略不计)。这些格线将纸分成了n×m 个大小完全相同的正方形小 格。你的同桌已经在每一块小格(i,j)上写下了一个互不相同的正整数P[i,j],
1<=P[i,j]<=n×m。 “他干嘛在纸上写下这么些数字呢?”你看着这些数字,疑惑不解。 这时,你的同桌突然出现了,他发现你正拿着他的纸,看着上面的数字发呆。 于是傻乎乎地对你说: “我刚刚也想学你折纸,可是我很笨,只折出一个1(cm)×1(cm)的正方形,也 就是一个n×m 层纸的纸垛,每一层恰好是一个小格,所有的格线都恰好在正方形 的边界上。” “哦,折得不错,挺好的。”你口里说不错,心里却暗笑:没见过你这么笨的。 居然把这么好的纸折成一个如此简单的正方形,简直是暴殄天物,罪过啊,罪过 “是吗?你也觉得不错啊?我刚刚就在想,如果给这些小格编上号,最上面 一层编为1,从上往下数的第i 层编为i,那么能不能从这些编号复原出刚刚我折 的那个图形呢?于是我就在这些格子上写下了它们的编号” “这……”你一时语塞,确切的说,惊讶得说不出话来,原来一向傻乎乎的同 桌脑子里也有这么深奥的想法。 “这样吧,如果你能根据我把我刚刚折的正方形折出来,那我就把这张纸送 给你!” 同桌接着说,“不管你折法是否和我一样,只要折出来也是个 1(cm)×1(cm)的正方形,从上往下数的第i 层的编号恰好也是i,并且纸不能破,就 算你折对了。” “好啊,不过我先要检查检查你有没有骗我,要是你故意骗我或者自己粗心 在编号的时候写错了数字而害得我折不出来,我可饶不了你!” 【输入文件】
第一行为整数t,代表输入数据的总数。 以下有t 组数据,每组数据的结构如下: 第一行两个正整数n,m。 以下n 行,每行m 个正整数,相邻两个整数之间用一个空格隔开,描述矩阵 p[i,j]。 【输出文件】 输出t 行,对应t 个输入数据。 对于第i 组数据,输出AllRight——如果可以折出来;输出Cheat——如果折 不出来。 【约定】 t ≤ 10 1 ≤ n,m ≤ 100 【样例输入】 4 1 7 3 1 7 6 5 4 2 2 2 1 2 3 4 2 3 2 1 6 3 4 5 4 4 11 12 15 14
10 9 16 13 5 8 1 2 9 7 4 3 【样例输出】 AllRight Cheat AllRight AllRight 【样例说明】 第四组数据的折法:
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4
1 7
3 1 7 6 5 4 2
2 2
1 2
3 4
2 3
2 1 6
3 4 5
4 4
11 12 15 14
10 9 16 13
5 8 1 2
6 7 4 3
AllRight
Cheat
AllRight
AllRight