我们假设NxM的基本地毯叫A,HxW的照片叫B.A和B都可以看作是一个二维矩阵.
B是大礼堂地毯的一部分,当且仅当能找到x和y满足:
直观来说就是找到B[0][0]对应的格子A[x][y],并且B的任意一个格子都与A循环拼接之后对应的格子相同.
于是我们很容易得到一个基本的思路:
这个每个判断的总时间复杂度是O(NMHW),有可能会超时.
优化的方法是,预先判断B是不是一个由某个NxM的基本地毯循环拼接得到的.
如果这一点不成立,那么答案就是NO.否则我们知道B是一个在横向上mod N循环,在纵向上mod M循环的二维矩阵.
那么就可以简化之前(2)的判断范围.我们不用判断B中的每个格子,而只要判断min(N H) x min(M W)这个范围内的格子即可.时间复杂度是O(NM).
所以判断一张照片的总时间复杂度是O(N^2M^2 + HW).