得分 : $1500$ 分

问题陈述

问题 F 和 F2 是相同的问题，但约束条件和时间限制不同。

我们有一个棋盘，分为 $N$ 行和 $N$ 列的正方形单元格。
从顶部第 $i$ 行和从左侧第 $j$ 列的单元格称为单元格 $(i,j)$。
每个单元格要么是空的，要么被障碍物占据。
此外，每个空单元格上都有一个数字。
如果 $A_{i,j}=$ 1、2、... 或 9，则单元格 $(i,j)$ 是空的，并且上面写有数字 $A_{i,j}$。
如果 $A_{i,j}=$ #，则单元格 $(i,j)$ 被障碍物占据。

当满足以下所有条件时，单元格 $Y$ 从单元格 $X$ 是 可达 的：

• 单元格 $X$ 和 $Y$ 不同。
• 单元格 $X$ 和 $Y$ 都是空的。
• 可以通过反复向右或向下移动到相邻的空单元格，从单元格 $X$ 到达单元格 $Y$。

考虑所有单元格对 $(X,Y)$，使得单元格 $Y$ 从单元格 $X$ 可达。
找出所有这些对中单元格 $X$ 和单元格 $Y$ 上数字的乘积的总和。

约束条件

• $1 \leq N \leq 1500$
• $A_{i,j}$ 是以下字符之一：1、2、... 9 和 #。

输入

输入从标准输入给出，格式如下：

$N$

$A_{1,1}A_{1,2}...A_{1,N}$

$A_{2,1}A_{2,2}...A_{2,N}$

$:$

$A_{N,1}A_{N,2}...A_{N,N}$

输出

打印所有对 $(X,Y)$ 中单元格 $X$ 和单元格 $Y$ 上数字乘积的总和，其中单元格 $Y$ 从单元格 $X$ 可达。

2
11
11

5

存在五对单元格 $(X,Y)$，使得单元格 $Y$ 从单元格 $X$ 可达，如下所示：

• $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$。

4
1111
11#1
1#11
1111

47

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

36065

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#########

6525