AT_agc028_f [AGC028F] Reachable Cells

[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

N/A

### 制約 - $ 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 $ になります。