CF677E Vanya and Balloons
题目描述
有一个挂着 $n\times n$ 个气球的棋盘，每个气球上有一个数字，数字只可能为 $0,1,2,3$ 中的一个。Vanya 要扎破一个十字形区域内的气球，使得这些气球上的数字乘积最大。
有两种“十字形区域”：一般形和旋转形，例如：
一般形：
```
**o**
**o**
ooooo
**o**
**o**
```
旋转形：
```
o***o
*o*o*
**o**
*o*o*
o***o
```
形式化地讲，十字形可如下定义：给定三个整数 $r,c,d$，满足 $d\leqslant r,c\leqslant n-d+1$。一般形的十字形由所有坐标满足 $|x-r|\cdot|y-c|=0$ 且 $|x-r|+|y-c|
输入格式
输入的第一行包括一个整数 $n$（$1\leqslant n\leqslant10^3$），表示棋盘的行数（也即列数），
接下来的 $n$ 行，每行包括 $n$ 个字符：'0', '1', '2' 或者 '3'，表示这一行气球上面的数字。
输出格式
输出可能得到的最大乘积对 $10^9+7$ 取模后的结果。
注意，你不需要保证最终得到的余数是最大的，而只需要计算出最大乘积对 $10^9+7$ 取模后的结果。
说明/提示
In the first sample, the maximum product is achieved for a rotated cross with a center in the cell $ (3,3) $ and radius $ 1 $ : $ 2·2·3·3·3=108 $ .