题解

题号这么小的黑题还没有题解，我给完善一下。

一个想法是枚举三块拼图和他们的旋转角度、是否翻转以及坐标，这样的复杂度是 O(K
3
N
4
) 的（忽略枚举方向的 8 倍常数）。

要优化这个算法，我们有以下方法：

定义一块拼图的左上坐标为其最左边的有颜色的单元格坐标，若有多个取最上面的坐标。若已知原拼图的左上坐标来自第 i 块拼图，则该位置来自第 i 块拼图的左上坐标；
使用哈希快速判断两块拼图是否相等。
第一个优化使得枚举前两块拼图时无需枚举其位置，第二个优化使得枚举第三块拼图时可以 O(1) 判断，时间复杂度来到 O(K
2
N
2
)。

如果 R,C 如题面说的一样在 100 之内，那这个复杂度确实是能过的（100
4
=10
8
），但是数据中 R,C 好像和 N,M 一个量级，再加上 8 倍常数的影响，肯定是无法通过的。这时需要一些剪枝：

枚举所有的 x,y,z，先判断一下这三块拼图是否在颜色个数和上和原拼图相等，这样可以筛出一些二元组 (i,j)，保证 i,j 同时存在的拼法一定非法。这样 O(K
2
) 就跑不满了；
对一块拼图，先枚举其 8 中不同的方向，如果其中有相同的，后面就不枚举它，这样 8 倍常数也跑不满；
对一块拼图，先计算出其左上坐标，判合法的时候就无需再算一次了，这样 O(N
2
) 带的常数变小。
这三个剪枝不容易同时卡掉至少两个（或者说数据没卡），可以通过。