実行時間制限: 4 sec / メモリ制限: 1024 MB
配点 : 1000 点
問題文
問題 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 500
- 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 にかかれている数字の積を求めたときの、その総和を出力せよ。
入力例 1
2 11 11
出力例 1
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 になります。
入力例 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
Score : 1000 points
Problem Statement
Problem F and F2 are the same problem, but with different constraints and time limits.
We have a board divided into N horizontal rows and N vertical columns of square cells.
The cell at the i-th row from the top and the j-th column from the left is called Cell (i,j).
Each cell is either empty or occupied by an obstacle.
Also, each empty cell has a digit written on it.
If A_{i,j}= 1
, 2
, ..., or 9
, Cell (i,j) is empty and the digit A_{i,j} is written on it.
If A_{i,j}= #
, Cell (i,j) is occupied by an obstacle.
Cell Y is reachable from cell X when the following conditions are all met:
- Cells X and Y are different.
- Cells X and Y are both empty.
- One can reach from Cell X to Cell Y by repeatedly moving right or down to an adjacent empty cell.
Consider all pairs of cells (X,Y) such that cell Y is reachable from cell X. Find the sum of the products of the digits written on cell X and cell Y for all of those pairs.
Constraints
- 1 \leq N \leq 500
- A_{i,j} is one of the following characters:
1
,2
, ...9
and#
.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the sum of the products of the digits written on cell X and cell Y for all pairs (X,Y) such that cell Y is reachable from cell X.
Sample Input 1
2 11 11
Sample Output 1
5
There are five pairs of cells (X,Y) such that cell Y is reachable from cell X, as follows:
- 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)
The product of the digits written on cell X and cell Y is 1 for all of those pairs, so the answer is 5.
Sample Input 2
4 1111 11#1 1#11 1111
Sample Output 2
47
Sample Input 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
Sample Output 3
36065
Sample Input 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#########
Sample Output 4
6525