题目描述

有一个由 $N$ 行 $N$ 列的格子组成的棋盘。自上而下的第 $i$ 行，自左而右的第 $j$ 列的格子记作 $(i,j)$。每个格子要么是空的，要么有障碍物。所有空格子上都写有一个数字。当 $A_{i,j}$ 为 1、2、...、9 时，表示格子 $(i,j)$ 是空的，且上面写着数字 $A_{i,j}$。当 $A_{i,j}$ 为 # 时，表示格子 $(i,j)$ 上有障碍物。

对于两个格子 $X$ 和 $Y$，若满足以下所有条件，则称“可以从格子 $X$ 到达格子 $Y$”：

• $X$ 和 $Y$ 是不同的格子。
• $X$ 和 $Y$ 都是空格子。
• 可以从 $X$ 出发，每次只向右或向下移动到相邻的空格子，最终到达 $Y$。

请计算所有满足“可以从格子 $X$ 到达格子 $Y$”的格子对 $(X,Y)$，将 $X$ 上的数字与 $Y$ 上的数字相乘后求和，输出这个总和。

输入格式

输入按以下格式从标准输入读入：

$N$
$A_{1,1}A_{1,2}\ldots A_{1,N}$
$A_{2,1}A_{2,2}\ldots A_{2,N}$
$\vdots$
$A_{N,1}A_{N,2}\ldots A_{N,N}$

输出格式

请输出所有满足“可以从格子 $X$ 到达格子 $Y$”的格子对 $(X,Y)$，将 $X$ 上的数字与 $Y$ 上的数字相乘后求和的结果。

输入输出样例 #1

输入 #1

2
11
11

输出 #1

5

输入输出样例 #2

输入 #2

4
1111
11#1
1#11
1111

输出 #2

47

输入输出样例 #3

输入 #3

10
76##63##3#
8445669721
75#9542133
3#285##445
749632##89
2458##9515
5952578#77
1#3#44196#
4355#99#1#
#298#63587

输出 #3

36065

输入输出样例 #4

输入 #4

10
4177143673
7#########
5#1716155#
6#4#####5#
2#3#597#6#
6#9#8#3#5#
5#2#899#9#
1#6#####6#
6#5359657#
5#########

输出 #4

6525

说明/提示

数据范围

• $1 \leq N \leq 1500$
• $A_{i,j}$ 是 1、2、...、9 或 # 之一。

样例解释 1

满足“可以从格子 $X$ 到达格子 $Y$”的格子对共有 $5$ 种：

• $X=(1,1)$，$Y=(1,2)$
• $X=(1,1)$，$Y=(2,1)$
• $X=(1,1)$，$Y=(2,2)$
• $X=(1,2)$，$Y=(2,2)$
• $X=(2,1)$，$Y=(2,2)$

对于每一组，$X$ 和 $Y$ 上的数字相乘都是 $1$，所以答案为 $5$。

由 ChatGPT 4.1 翻译