当前位置: 代码迷 >> 综合 >> UVa 201 Squares(正方形)
  详细解决方案

UVa 201 Squares(正方形)

热度:74   发布时间:2023-12-08 11:25:18.0


题意:

有n行n列(2<=n<=9)的小黑点,还有m条线段连接其中的一些黑点。统计这些线段连成了多少正方形。(每种边长分别统计)。

行从上到下编号为1~n,列从左到右编号为1~n。边用H i j和V i j表示,分别代表(i,j)-(i,j+1)和(i,j)-(i+1,j)。


思路:

读入的时候,先对每个点是否存在先左或向下的边做标记。然后统计从这点开始向左和向下的最大边长。如果要判断是否存在以(i,j)为左上顶点的边长为len的正方形,只需要判断以(i,j)为起点向左和向下的最大边长,以(i+len,j)为起点