简单动态规划

预处理出矩阵中每个点，向上下左右最多能衍生的距离。这个可以用dp数组简单转移出来，类似前缀和:

例如:向上衍生的距离为:

当 $a[i][j] = a[i - 1][j]$ , $up[i][j] = up[i - 1][j] + 1$

否则$up[i][j] = 0$

题目描述

小欧有一个只包含 0和1的矩阵，他定义矩阵上一个结点的可视化距离为结点在竖直方向上能看到的与其值相等的结点数量与结点在水平方向上能看到与其值相等的结点数量之和。(若中间被一个值不相等的结点数量阻挡，则该结点无法再看到之后的结点)

例如:

矩阵

1011

1101

0101

1010

中，结点(2,2)的可视化距离为 2，他只能看到(2,1) 和(3,2) 两个结点

矩阵

1011

0110

0101

1110

中，结点(2,2)的可视化距离为 3，他只能看到(2,3)、 (3,2) 和(4,2)。

小欧想知道，矩阵所有结点的可视化距离之和是多少?

输入描述

第一行输入一个正整数n($1 \leq n \leq 1000$) 接下来的n行，每行输入一个长度为n的字符串,只包含0和1

输出描述

一行一个整数，矩阵所有节点的可视化距离之和

示例1

输入

4
1011
1101
0101
1010

输出

16