分数: 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 is 可达 来自单元格 X 当以下条件全部满足时:
- 细胞 X 和 Y 不同。
- 细胞 X 和 Y 都是空的。
- 可以从 Cell 到达 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.
示例输入 1
2 11 11
示例输出 1
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 is 1 对于所有这些对,所以答案是 5.
示例输入 2
4 1111 11#1 1#11 1111
示例输出 2
47
示例输入 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
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