#P3934. [CQOI2015]标识设计

    ID: 3136 传统题 1000ms 512MiB 尝试: 303 已通过: 103 难度: 8 上传者: 标签>CF2400提高+/省选-轮廓线 DP计数 DP状态编码滚动数组预计算转移

[CQOI2015]标识设计

[CQOI2015] 标识设计

题目描述

给定一个 nn 行 mm 列的方格板,每个格子要么是空白,要么已放有装饰。请在空白格上放置恰好三个相互不重叠的 L 形图案。

每个 L 的方向与大写字母 L 一致。竖笔从拐角向上延伸,横笔从拐角向右延伸,两个方向都至少延伸一个格子。不能旋转或翻转。L 的所有格子必须位于方格板内且为空白格。

空白格可以不被任何 L 使用。三个 L 没有编号,交换它们的顺序不会产生新方案。

求不同放置方案的数量。

原题 L 形图案示意

原题存档的文字称必须占满方格,但示意图留有白格,样例的四种放置也都留有空格。本站按样例与评测的含义计数。

输入格式

第一行两个整数 n,mn,m。

接下来 nn 行,每行 mm 个字符。# 表示已放有装饰的格子,. 表示空白格。

输出格式

输出一个整数,表示放置方案数。

样例

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

数据范围

2≤n,m≤302\le n,m\le30。

BZOJ 原题存档