题目 3231:
蓝桥杯2024年第十五届省赛真题-LITS 游戏
时间限制: 3s
内存限制: 512MB 提交: 157 解决: 4
题目描述
俄罗斯方块是一款风靡全球的游戏，在游戏中有多种方格图案，我们只关注这四个经典的方块图案：LITS，如下图所示：
LITS 这四种方块都是由四个相同大小的小方块组成的。
现在给出一副大小为 N × N 的格子图，每个格子上都有一个数字 0/1，如果格子处的数字为 1 说明这个格子上有一个小方块，数字为 0 则没有。你需要判断从这个格子图上是否可以找出 LITS 四个方块图案（每个方块图案之间都是独立的，不存在不同的图案公用同一个小方块的情况）。其中LITS 方块的形状旋转任意个 90 度都是合法的，但不允许翻转。
输入格式
第一行一个整数 T，表示有 T 组数据。
每组数据的第一行包含一个整数 N，表示格子图大小。
接下来输入 N 行，每行 N 个值为 0/1 的整数，表示格子布局。
输出格式
对于每组数据，输出一行包含一个字符串。如果此组数据满足题意则输出“Yes”，否则输出 “No”。
样例输入
2 5 1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 5 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1
样例输出
No Yes
提示
【样例说明】
对于样例中的第二个格子图，一种 LITS 的摆放方案如下：
1 0 0 1 1
L S T T T
L S S T 0
L L S 0 1
0 I I I I
【评测用例规模与约定】
对于 30% 的评测用例：1 ≤ N ≤ 5。
对于 60% 的评测用例：1 ≤ N ≤ 10。
对于 100% 的评测用例：1 ≤ T ≤ 10，1 ≤ N ≤ 50。