《大礼堂地毯》题目分析

我们假设NxM的基本地毯叫A，HxW的照片叫B。A和B都可以看作是一个二维矩阵。

B是大礼堂地毯的一部分，当且仅当能找到x和y满足：

B[i][j] = A[(i + x) mod N][(j + y) mod M] 且 0 <= x < N, 0 <= y < M。

直观来说就是找到B[0][0]对应的格子A[x][y]，并且B的任意一个格子都与A循环拼接之后对应的格子相同。

于是我们很容易得到一个基本的思路：

(1) 首先枚举B[0][0]对应的格子A[x][y]，复杂度是O(NM)。

(2) 然后判断每一个格子B[i][j]是不是与A循环拼接之后对应的格子A[(i + x) mod N][(j + y) mod M]相同，复杂度是O(HW)。

这个每个判断的总时间复杂度是O(NMHW)，有可能会超时。

优化的方法是，预先判断B是不是一个由某个NxM的基本地毯循环拼接得到的。

如果B是由A循环拼接得到的，那么B必然满足B[i][j] = B[i+N][j]和B[i][j] = B[i][j+M]。判断这一点的时间复杂度是O(HW)。

如果这一点不成立，那么答案就是NO。否则我们知道B是一个在横向上mod N循环，在纵向上mod M循环的二维矩阵。

那么就可以简化之前(2)的判断范围。我们不用判断B中的每个格子，而只要判断min(N, H) x min(M, W)这个范围内的格子即可。时间复杂度是O(NM)。

所以判断一张照片的总时间复杂度是O(N^2M^2 + HW)。