QOJ.ac

QOJ

実行時間制限: 6 s メモリ制限: 2048 MB 満点: 100

#2435. 三角形

統計

在前往北京的旅途中,你带了许多益智书,其中许多书里都有类似这样的挑战:图 I.1 中有多少个三角形?

图 I.1:样例输入 2 的示意图。

虽然这些谜题能让你暂时感兴趣,但你很快就会对它们感到厌倦,转而开始思考如何用算法来解决它们。谁知道呢,也许这样的问题真的会出现在今年的比赛中。好吧,你猜怎么着?今天就是你的幸运日!

输入格式

输入的第一行包含两个整数 $r$ 和 $c$ ($1 \le r \le 3\,000, 1 \le c \le 6\,000$),指定了图片的大小,其中 $r$ 是顶点的行数,$c$ 是列数。接下来有 $2r - 1$ 行,每行最多包含 $2c - 1$ 个字符。奇数行包含网格顶点(用小写字母 x 表示)和零个或多个水平边,而偶数行包含零个或多个对角边。具体来说,编号为 $4k + 1$ 的行在位置 $1, 5, 9, 13, \dots$ 处有顶点,而编号为 $4k + 3$ 的行在位置 $3, 7, 11, 15, \dots$ 处有顶点。输入中表示了所有可能的顶点(例如,参见样例输入 2 中图 I.1 的表示方式)。连接相邻顶点的水平边用三个短横线表示。对角边用单个正斜杠('/')或反斜杠('\')字符表示。边字符将精确放置在对应顶点之间。所有其他字符均为空格。注意,如果任何输入行包含尾随空格,则这些空格可能会被省略。

输出格式

显示输入图片中由网格边形成的三角形(任意大小)的数量。

样例

样例输入 1

3 3
x---x
\ /
x
/ \
x x

样例输出 1

1

样例输入 2

4 10
x x---x---x x
\ / / \
x x---x x x
/ \ / \ \
x x---x---x---x
/ / \ \ / \
x---x---x---x---x

样例输出 2

12

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.