题目描述

問題 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$ にかかれている数字の積を求めたときの、その総和を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ にかかれている数字の積を求めたときの、その総和を出力せよ。

题目大意

给定一张 $N$行 $N$列的网格图，每一个格子有两种情况：有障碍物，或者是空的并且写着一个 $1\sim 9$的整数。

称格子 $Y$能被格子 $X$到达当且仅当以下条件均被满足：

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

求出 $\sum A_XA_Y$，其中 $X$可以到达 $Y$，A代表格子上的数。

2
11
11

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

提示

制約

• $1\ \leq\ N\ \leq\ 1500$
• $A_{i,j}$ は 1, 2, ... 9, # のうちいずれかの文字である。

Sample Explanation 1

マス $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$ になります。