← 返回题目列表

Codeforces · 2172/K

K. 幼儿园作业

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

肯尼是一名幼儿园老师,正在教学生数学。为了帮助他们学习,他希望以一种有趣且不烦人的形式给他们布置作业——数字搜索。

数字搜索谜题与单词搜索谜题类似,但它不是寻找单词,而是寻找数学表达式。拼图实例由两部分组成:包含 $$$n$$$ 行和 $$$m$$$ 列的网格,以及要搜索的 $$$q$$$ 目标数字的列表 $$$a_1、a_2、\dots、a_q$$$。网格中的每个单元格包含一个数字 1 to 9,一个加号 +或乘号 *.

可以通过沿同一行、列或对角线以直线(任一方向)连接一个或多个连续字符来形成表达式。每个表达式都可以通过其起始单元格和结束单元格来定义。如果两个表达式在不同的单元格处开始或结束,即使它们包含完全相同的字符,也被认为是不同的。

有效表达式的格式必须为 $$num \quad op \quad num \quad op \ \dots \ op \quad num$$,其中每个 $$$num$$$ 是一个或多个数字的序列,每个 $$$op$$$ 是 + or *。例如,“123“和”1+2*3+45" 是有效表达式,而 "+123“和”2**5“不是。表达式的值是按照典型算术规则求值的结果。

该谜题的目标是计算,对于每个数字 $$$a_i$$$,网格中有多少个不同的有效表达式计算结果为 $$$a_i$$$。

为了演示规则,请考虑以下已完成的数字搜索谜题:

让我们将 $$$r$$$ 行和 $$$c$$$ 列的单元格表示为 $$$(r,c)$$$。

  1. $$$67$$$ 的答案是 $$$2$$$,因为有两个表达式 "67" 从 $$$(1, 4)$$$ 开始。尽管两个表达式包含相同的字符,但它们被视为不同,因为它们以不同的位置结束。
  2. $$$420$$$ 的答案是 $$$0$$$,因为网格中没有表达式计算结果为 $$$420$$$。
  3. $$$3$$$ 的答案是 $$$4$$$:
    • 表达式“3" 出现两次,分别在 $$$(1,7)$$$ 和 $$$(9,5)$$$ 处。
    • 表达式“1+2"出现从$$$(6,2)$$$到$$$(8,2)$$$。
    • 表达式“2+1"出现从$$$(8,2)$$$到$$$(6,2)$$$。即使它们共享同一组单元格,但这两个表达式也被认为是不同的,因为它们从不同的位置开始。
  4. $$$727$$$ 的答案是 $$$3$$$:
    • 表达式“7+16*45"从$$$(2,1)$$$到$$$(8,7)$$$出现。请注意,乘法在加法之前执行。
    • 表达式“727"出现在从$$$(3,5)$$$到$$$(3,7)$$$,以及从$$$(3,7)$$$到$$$(3,5)$$$。尽管它们共享同一组单元格并包含相同的字符,但它们仍被视为不同,因为它们从不同的位置开始。

肯尼迫不及待地想看到孩子们喜欢解决有趣的数字搜索谜题。但在给他们出难题之前,他需要准备好答案。请帮助他计算他准备的每个谜题的答案。

输入

第一行包含三个整数$$$n$$$、$$$m$$$和$$$q$$$,分别代表行数、列数和目标数字的数量。

以下 $$$n$$$ 行中的每一行都包含 $$$m$$$ 个字符的字符串,代表网格。

以下 $$$q$$$ 行中的第 $$$i$$$ 行包含一个整数 $$$a_i$$$,表示第 $$$i$$$ 个目标数字。

  • $$$1 \leq n, m \leq 1000$$$
  • $$$1 \leq n \times m \leq 3 \times 10^4$$$
  • $$$1 \leq q \leq 10^5$$$
  • 网格仅包含“中的字符123456789+*".
  • $$$1 \leq a_i \leq 10^6$$$
  • 所有 $$$a_i$$$ 都是不同的。

输出

打印 $$$q$$$ 行。第 $$$i$$$ 行包含一个整数,表示 $$$a_i$$$ 的答案。

示例

输入
复制

9 8 4
4216793+
717*4*54
7+5+727*
45149+71
8+26697*
+189*2+9
5+*244+7
42595952
97+*315+
67
420
3
727

输出
复制

2
0
4
3