配点 : $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)$ には障害物が置かれています。

マス $X$ からマス $Y$ に到達可能であるとは、以下の条件をすべて満たすことを意味します。

• マス $X$, $Y$ は相異なる。
• マス $X$, $Y$ はどちらも空である。
• マス $X$ から出発し、右または下に隣接する空マスへの移動を繰り返すことで、マス $Y$ に到達できる。

マス $X$ からマス $Y$ に到達可能であるようなマスの組 $(X,Y)$ すべてについて、マス $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)$ すべてについて、マス $X$ にかかれている数字とマス $Y$ にかかれている数字の積を求めたときの、その総和を出力せよ。

2
11
11

5

マス $X$ からマス $Y$ に到達可能であるようなマスの組 $(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$ になります。

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