68 人解决,94 人已尝试。
69 份提交通过,共有 308 份提交。
4.2 EMB 奖励。
单点时限: 1.0 sec
内存限制: 512 MB
给定一张 $n \times n$ 的网格图,部分点为黑色,其余点为白色,请你统计其中 $S$ 图的数量。
大小为 $k$ 的 $S$ 图定义为:
1. 由 $5$ 条长度为 $k$ 的线段组成 $(k \geqslant 1)$
2. $5$ 条线段首尾相连,且只覆盖黑色的点(注意是线段上的所有格点均为黑色,而不仅仅是端点)
3. 形如 “S”,即 $5$ 条线段的端点坐标如下:
$\quad (a,b),(a, b- k)$
$\quad (a,b-k),(a+k, b- k)$
$\quad (a+k,b-k),(a+k, b)$
$\quad (a+k,b),(a+2k, b)$
$\quad (a+2k,b),(a+2k, b-k)$
注意,我们认为网格图从上到下编号依次为 $1$ 到 $n$,从左到右编号依次为 $1$ 到 $n$。
例如,下图包含一张大小为 $5$ 的 $S$ 图。
注意,下图不包含 $S$ 图。
输入的第一行包含一个整数 $n \ (1 \leqslant n \leqslant 50)$,表示网格图的大小。
接下来 $n$ 行,每行一个长度为 $n$ 的字符串 $s_i \ (1 \leqslant i \leqslant n)$。
用 $s_{i, j}$ 表示 $s_i$ 的第 $j \ (1 \leqslant j \leqslant n)$ 个字符 $(s_{i,j} \in \lbrace$ o
, x
$\rbrace)$,$s_{i,j} = $o
表示网格图中从上到下第 $i$ 行、从左到右第 $j$ 列的点为白色,$s_{i, j} = $x
表示点为黑色。
输出一行一个整数,表示网格图中 $S$ 图的数量。
3 xxo xxo xxo
1
4 ooxx ooxx ooxx ooxx
2
3 xxx xox xxx
0
68 人解决,94 人已尝试。
69 份提交通过,共有 308 份提交。
4.2 EMB 奖励。
创建: 7 月,4 周前.
修改: 7 月,3 周前.
最后提交: 6 月前.
来源: N/A