CF1106A.Lunar New Year and Cross Counting

入门

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Lunar New Year is approaching, and you bought a matrix with lots of "crosses".

This matrix MM of size n×nn \times n contains only 'X' and '.' (without quotes). The element in the ii-th row and the jj-th column (i,j)(i, j) is defined as M(i,j)M(i, j), where 1≤i,j≤n1 \leq i, j \leq n. We define a cross appearing in the ii-th row and the jj-th column (1<i,j<n1 \lt i, j \lt n) if and only if $M(i, j) = M(i - 1, j - 1) = M(i - 1, j + 1) = M(i + 1, j - 1) = M(i + 1, j + 1) = $ 'X'.

The following figure illustrates a cross appearing at position (2,2)(2, 2) in a 3×33 \times 3 matrix.

X.X
.X.
X.X

Your task is to find out the number of crosses in the given matrix MM. Two crosses are different if and only if they appear in different rows or columns.

农历新年即将来临,你买了一个包含大量“十字形”的矩阵。

这个大小为 n×nn \times n 的矩阵 MM 仅由字符 'X' 和 '.'(不含引号)组成。第 ii 行第 jj 列的元素(其中 1≤i,j≤n1 \leq i, j \leq n)记为 M(i,j)M(i, j)。我们定义:当且仅当 $M(i, j) = M(i - 1, j - 1) = M(i - 1, j + 1) = M(i + 1, j - 1) = M(i + 1, j + 1) = $ 'X' 时,矩阵中在第 ii 行第 jj 列(满足 1<i,j<n1 \lt i, j \lt n)处出现一个十字形。

下图展示了一个 3×33 \times 3 矩阵中位于位置 (2,2)(2, 2) 的十字形:

X.X
.X.
X.X

你的任务是计算给定矩阵 MM 中十字形的总数。两个十字形不同,当且仅当它们出现在不同的行或列。

输入格式

The first line contains only one positive integer nn (1≤n≤5001 \leq n \leq 500), denoting the size of the matrix MM.

The following nn lines illustrate the matrix MM. Each line contains exactly nn characters, each of them is 'X' or '.'. The jj-th element in the ii-th line represents M(i,j)M(i, j), where 1≤i,j≤n1 \leq i, j \leq n.

第一行仅包含一个正整数 nn(1≤n≤5001 \leq n \leq 500),表示矩阵 MM 的大小。

接下来的 nn 行描述矩阵 MM。每行恰好包含 nn 个字符,每个字符为 'X' 或 '.'。第 ii 行的第 jj 个元素表示 M(i,j)M(i, j),其中 1≤i,j≤n1 \leq i, j \leq n。

输出格式

Output a single line containing only one integer number kk — the number of crosses in the given matrix MM.

输出一行,仅包含一个整数 kk —— 给定矩阵 MM 中“十”字形图案的数量。

输入输出样例

  • 输入#1

    5
    .....
    .XXX.
    .XXX.
    .XXX.
    .....

    输出#1

    1
  • 输入#2

    2
    XX
    XX

    输出#2

    0
  • 输入#3

    6
    ......
    X.X.X.
    .X.X.X
    X.X.X.
    .X.X.X
    ......

    输出#3

    4

说明/提示

In the first sample, a cross appears at (3,3)(3, 3), so the answer is 11.

In the second sample, no crosses appear since n<3n \lt 3, so the answer is 00.

In the third sample, crosses appear at (3,2)(3, 2), (3,4)(3, 4), (4,3)(4, 3), (4,5)(4, 5), so the answer is 44.

在第一个样例中,十字形出现在 (3,3)(3, 3) 处,因此答案为 11。

在第二个样例中,由于 n<3n \lt 3,不存在任何十字形,因此答案为 00。

在第三个样例中,十字形出现在 (3,2)(3, 2)、(3,4)(3, 4)、(4,3)(4, 3)、(4,5)(4, 5) 处,因此答案为 44。

输入解题思路,AI测评打分。不知道怎么写?

首页