← 返回题目列表

AtCoder · agc028_f2

F2. 可到达的单元格

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

分数: 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