← 返回题目列表

AtCoder · abc430_b

C. 计数子网格

中文机器翻译题面 查看原题

分数: 250 点

问题陈述

有一个网格 N 行和 N 列。牢房位于 i从顶部开始的第行和 j如果满足以下条件,则从左侧算起的第 - 列将被涂成黑色: S_{i,j} is #,如果是白色 ..

通过提取一个区域可以得到多少种不同的绘制细胞图案 M 行和 M 此网格中的列?

约束

  • 1\leq M \leq N \leq 10
  • N 和 M 是整数。
  • S_{i,j} is . or #.

输入

输入由标准输入按以下格式给出:

N M
S_{1,1}\ldots S_{1,N}
\vdots
S_{N,1}\ldots S_{N,N}

输出

打印答案。


示例输入 1

3 2
...
###
#.#

示例输出 1

3

给定网格的状态如下左图所示。
有四种方法可以从该网格中提取两行两列的区域,如下右图所示,并且绘制的单元格有三种不同的模式。

Figure


示例输入 2

10 3
..#.......
.###......
.#.#......
#####.....
#...#.....
......####
......#..#
......#...
......#..#
......####

示例输出 2

36