题目详情题解（0）讨论（0）提交记录（0）

AT_abc430_b.[ABC430B] Count Subgrid

入门

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 NN 行 NN 列的网格。如果第 ii 行第 jj 列的格子 Si,jS_{i,j} 为 #，则该格子为黑色；如果为 .，则为白色。

通过从这个网格中提取一个 MM 行 MM 列的区域，最多可以获得多少种不同的染色方案？

输入格式

输入按以下格式从标准输入给出：

N MN\ M
S1,1…S1,NS_{1,1}\ldots S_{1,N}
⋮\vdots
SN,1…SN,NS_{N,1}\ldots S_{N,N}

输出格式

输出不同的染色方案的数量。

输入输出样例

  • 输入#1

    3 2
...
###
#.#

    输出#1

    3

  • 输入#2

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

    输出#2

    36

说明/提示

样例解释1

给定网格如左图所示。
如下图右侧所示，有四种方式可以选取两行两列的区域，而这四种方案实际产生了三种不同的染色模式。

图片

数据范围

  • 1≤M≤N≤101\leq M\leq N\leq 10
  • NN 和 MM 为整数。
  • Si,jS_{i,j} 仅为 . 或 #。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页