TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3253
  • 题目
  • P3253【CQOI2015】标识设计
    限制 : 时间限制 : 40000 MS   空间限制 : 524288 KB
    问题描述

            一家名字缩写为LLL的公司正在设计logo,他们的初步方案是在一张方格上放置3个L形的图案以及一些额外的装饰性图形。例如:
    (灰色区域表示装饰性图形)
            3个L图案和装饰性图形均放置在方格之中,且必须占满方格。"L"的横竖笔画长短均可,但长度必须大于0(即不能退化为一条线段)。另外,为了使L图案醒目且容易辨别,设计师规定3个L形图案之间不能有重叠或交叉的部分。当然,L形图案也不能穿过装饰图形或与之重叠。
            现在设计师已经确定了所有装饰性图形的位置,希望你计算一下放置不同的L形图案总共可以设计出多少个logo。

    输入格式

            输入文件第一行包含两个空格分开的正整数n和m,分别表示方格的行数和列数。
            接下来n行,每行m个字符,为"."或"#"。"#"表示该方格为装饰性图形,"."表示可以放置L图案的空白区域。

    输出格式

            输出一个整数,为可能的logo总数。

    样例输入

    4 4
    ....
    #...
    ....
    ..#.

    样例输出

    4

    提示

    样例解释

            满足要求的logo只有这4种。注意,颜色只是为了便于说明,不影响方案数,因为在实际的logo中3个L图案将使用相同的色彩、纹理和光泽。

    数据范围
            对于30%的数据,n,m≤5。
            对于100%的数据,2≤n,m≤30。