/ Vijos / 题库 /

正方形内的计数

正方形内的计数

背景

Orz4-4 Square

描述

爱偷懒的小X这次玩起了一个幼稚的游戏。他拿出若干相同长度的火柴棍,在地上摆了起来。摆着摆着小X发现火柴不够,不能按原先的设想摆出一个N×N的正方形网格。只剩下最后一根火柴了,于是小X把这根火柴交给了LHX教主。小X只有一个要求,就是在现有的基础上能让这个不怎么好看的网格再多出至少一个正方形(你可以认为一个2×2完整网格有5个正方形)。

但是LHX教主为了显示他足够NB,他想把所有满足要求的位置都告诉小X。现在假如你就是LHX教主,你只需要输出有多少个位置放下一根火柴后可以让整个网格多出至少一个正方形。

格式

输入格式

第1行为一个**正整数**N,表示网格是不大于N×N的。

接下来N+1行,每行均有N×2+1个字符

设网格左上角格点为(1, 1),右下角格点为(N+1, N+1),也就是其中(x, y)表示了第x行第j列的格点。

对于接下来这N+1行,若有一根连接格点(i, j)与(i, j+1)的火柴,那么第i行,第j×2个字符为“_”;若有一根连接格点(i, j)与(i+1, j)的火柴,那么第i+1行,第j×2-1个字符为“|”。其余位置的字符均为空格。

输出格式

仅包括一个**非负整数**,为满足要求的位置数。

样例1

样例输入1

3
 _ _ _ 
|    _|
|  _  |
|_| |_|

样例输出1

4

限制

对于20%的数据,有N≤10;
对于40%的数据,有N≤100;
对于100%的数据,有N≤1000;

时限2s。

提示

_ _ _
| 1_|
|. _ .|
|_|.|_|
.表示标出的横着的火柴,1表示标出的竖着的火柴。在标出的位置放入对应火柴均可使原不完整网格多出至少1个正方形。其中将火柴放入最下面的那个标出的位置可以多出2个正方形,但是仍然只算作是一个位置。

(友情提示,上图在VIJOS可能显示可能会出现一些问题,建议复制到记事本下查看)

信息

ID
1618
难度
8
分类
搜索 | 枚举数据结构 | 树状数组 点击显示
标签
递交数
344
已通过
32
通过率
9%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Orz教主第四次模拟赛