这道题首先我们发现只要固定正方形两条相邻边,就可以得到这个正方形的具体信息。 但是直接固定两条边需要枚举三个点,复杂度比较高。
我们完全可以枚举一条边,然后将这条边顺时针或者逆时针旋转90度,从而实现固定两条边。这样只需要枚举两个点即可。
然后一个正方形按照这样的寻找策略会被找到4次,因此最后答案要除4。
在一片由 n 行 m 列单元格构成的矩形区域内,某些单元格被视为特殊点。你需要选出四个不同的特殊点,使得它们恰好构成一个正方形的四个顶点。正方形的边可以不与网格的边界平行,即正方形可以是倾斜的。 两个正方形被视为相同当且仅当它们对应的四个顶点位置集合完全相同,与顶点的选取顺序无关。请计算一共有多少个不同的正方形。
保证网格的行数 n 和列数 m 均不超过 50,每个单元格用字符 '.' 或 'X' 表示,其中 'X' 表示该格子是特殊点。
第一行包含两个整数 n 和 m,分别表示网格的行数与列数(1≤n,m≤50)。
接下来 n 行,每行包含一个长度为 m 的字符串,仅由字符 '.' 和 'X' 构成,'X' 表示对应位置的单元格是特殊点。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册