/ Vijos / 题库 /

菱形内的计数

菱形内的计数

描述

教主上电视了!这个消息绝对是一个爆炸性的新闻。一经传开,大街上瞬间就没人了(都回家看电视去了),商店打烊,工厂停业。大家都把电视机的音量开到最大,教主的声音回响在大街小巷。

小L给小X慌乱地打开自己家的电视机,发现所有频道都播放的是教主的采访节目(-_-bbb)。只见电视屏幕上的教主笑意吟吟,给大家出了一道难题:
一个边长为n的大菱形被均匀地划分成了n*n个边长为1的小菱形组成的网格,但是网格中部分边被抹去了,小L想知道,大菱形内有多少个平行四边形,这些平行四边形内不存在边(平行四边形内是空的)。

教主说,如果谁写出了程序,移动用户请将程序发送到xxxx,联通用户请将程序发送到xxxx……如果答对这个题,将有机会参加抽奖,大奖将是教主签名的Orz教主T-Shirt一件!这个奖品太具有诱惑力了。于是你需要编一个程序完成这么一道题。

格式

输入格式

输入的第1行为一个正整数n,为大菱形的边长。

以下2n行,每行2n个字符,字符为空格,“/”,“\”中的一个。

前n行,第i行中居中有2i个字符,这2i个字符中位置为奇数的字符只可能为“/”或者空格,位置为偶数的字符只可能为“\”或空格,若为空格表示这样一条边不存在,其余字符均为空格,描述了大菱形的上半部分。

后n行,第i行居中有有2(n-i+1)个字符,与上半部分类似地描述了菱形的下半部分
输入文件保证大菱形的轮廓上没有边被抹去。

输出格式

输出仅包括一个整数,为满足要求的平行四边形个数。

样例1

样例输入1

3
  /\  
 /\/\ 
/ /\ \
\/\  /
 \ \/ 
  \/  

样例输出1

3

限制

对于20%的数据,n≤10;
对于40%的数据,n≤60;
对于60%的数据,n≤200;
对于100%的数据,n≤888。

时限1s

来源

TangKy

信息

ID
1467
难度
4
分类
搜索 | 动态规划 点击显示
标签
递交数
147
已通过
57
通过率
39%
被复制
2
上传者

相关

在下列训练计划中:

星辰大海中闪烁的趣题

RP++分类题库

在下列比赛中:

Orz教主第2次模拟赛