#6411. 「ICPC World Finals 2018」三角形

内存限制:1024 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

来到北京前,你准备了不少童书,许多书包含了像这样的问题:下图中有多少个三角形?

无标题.png

尽管这些题一开始吸引了你的兴趣,但你很快感到无聊,希望用算法来解决这样的问题。说不定今年的比赛会考到这样的问题,谁知道呢。所以今天你很幸运!

输入格式

第一行有两个整数 r c (1 \le r \le 3\ 000,1 \le c \le 6\ 000) ,表示图片的大小,其中 r 是顶点的行数, c 是列数。接下来有 2r-1 行,每行至多有 2c-1 个字符。奇数行为顶点(用小写字母 x 表示)及不少于 0 个水平边,偶数行则有不少于 0 条对角线。特别地,形如 4k+1 的行号在 1,5,9,13,... 位置上有顶点,而形如 4k+3 的行号在 3,7,11,15,... 位置上有顶点。所有可能出现的顶点都在输入中(见图和样例 2)。连接相邻顶点的水平边用三条横线表示,对角线用一个斜杠 / 或反斜杠 \ 表示,恰好放在对应的顶点之间。其它的字符都是空格。注意如果一行末尾有空格,这个空格可能被省略。

输出格式

输出原图网格形成的三角形(不限大小)的个数。

样例

样例输入 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

数据范围与提示

在不侵犯原题版权的情况下,本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布,注明出处时需指向本题链接。