[AGC028F] Reachable Cells

给定一张 $N$行 $N$列的网格图，每一个格子有两种情况：有障碍物，或者是空的并且写着一个 $1\sim 9$的整数。 称格子 $Y$能被格子 $X$到达当且仅当以下条件均被满足： - 单元格 $X$和 $Y$不同。 - 单元格 $X$和 $Y$均为空。 - 通过反复向右或向下移动到相邻的空单元格，可以从单元格 $X$到达单元格 $Y$。 求出 $\sum A_XA_Y$，其中 $X$可以到达 $Y$，A代表格子上的数。

[problemUrl]: https://atcoder.jp/contests/agc028/tasks/agc028_f **問題 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 $ にかかれている数字の積を求めたときの、その総和を出力せよ。

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\ 500 $ - $ 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 $ になります。