AT_agc028_f [AGC028F] Reachable Cells

有一个由 $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}\ldots A_{1,N}$ > $A_{2,1}A_{2,2}\ldots A_{2,N}$ > $\vdots$ > $A_{N,1}A_{N,2}\ldots A_{N,N}$

请输出所有可以从 $X$ 到 $Y$ 的格子对 $(X,Y)$，$X$ 上的数字与 $Y$ 上的数字的乘积之和。

### 数据范围 - $1 \leq N \leq 500$ - $A_{i,j}$ 只会是 `1`, `2`, ... `9`, `#` 这几种字符之一。 ### 样例解释 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$。 由 ChatGPT 4.1 翻译