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|<d$ 的气球构成；旋转形的十字形由所有坐标满足 $|x-r|=|y-c|$ 且 $|x-r|<d$ 的气球构成。其中 $x,y$ 分别为气球的横纵坐标。 Vanya 想知道扎破的十字形区域内气球上数字的乘积的最大值，考虑到答案可能很大，故只需要输出答案对 $10^9+7$ 取模后的值。 ### 输入格式 输入的第一行包括一个整数 $n$（$1\leqslant n\leqslant10^3$），表示棋盘的行数（也即列数）， 接下来的 $n$ 行，每行包括 $n$ 个字符：'0', '1', '2' 或者 '3'，表示这一行气球上面的数字。 ### 输出格式 输出可能得到的最大乘积对 $10^9+7$ 取模后的结果。 注意，你不需要保证最终得到的余数是最大的，而只需要计算出最大乘积对 $10^9+7$ 取模后的结果。

题目描述

Vanya plays a game of balloons on the field of size $ n×n $ , where each cell contains a balloon with one of the values $ 0 $ , $ 1 $ , $ 2 $ or $ 3 $ . The goal is to destroy a cross, such that the product of all values of balloons in the cross is maximum possible. There are two types of crosses: normal and rotated. For example: `<br></br>**o**<br></br>**o**<br></br>ooooo<br></br>**o**<br></br>**o**<br></br>`or `<br></br>o***o<br></br>*o*o*<br></br>**o**<br></br>*o*o*<br></br>o***o<br></br>`Formally, the cross is given by three integers $ r $ , $ c $ and $ d $ , such that $ d<=r,c<=n-d+1 $ . The normal cross consists of balloons located in cells $ (x,y) $ (where $ x $ stay for the number of the row and $ y $ for the number of the column), such that $ |x-r|·|y-c|=0 $ and $ |x-r|+|y-c|&lt;d $ . Rotated cross consists of balloons located in cells $ (x,y) $ , such that $ |x-r|=|y-c| $ and $ |x-r|&lt;d $ . Vanya wants to know the maximum possible product of the values of balls forming one cross. As this value can be large, output it modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

The first line of the input contains a single integer $ n $ ( $ 1<=n<=1000 $ ) — the number of rows and columns in the table with balloons. The each of the following $ n $ lines contains $ n $ characters '0', '1', '2' or '3' — the description of the values in balloons.

输出格式

Print the maximum possible product modulo $ 10^{9}+7 $ . Note, that you are not asked to maximize the remainder modulo $ 10^{9}+7 $ , but to find the maximum value and print it this modulo.

输入输出样例

输入样例 #1

4
1233
0213
2020
0303

输出样例 #1

108

输入样例 #2

5
00300
00300
33333
00300
00300

输出样例 #2

19683

输入样例 #3

5
00003
02030
00300
03020
30000

输出样例 #3

108

输入样例 #4

5
21312
10003
10002
10003
23231

输出样例 #4

3

输入样例 #5

5
12131
12111
12112
21311
21212

输出样例 #5

24

说明

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 $ .

题意翻译

### 题目描述 有一个挂着 $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|<d$ 的气球构成；旋转形的十字形由所有坐标满足 $|x-r|=|y-c|$ 且 $|x-r|<d$ 的气球构成。其中 $x,y$ 分别为气球的横纵坐标。 Vanya 想知道扎破的十字形区域内气球上数字的乘积的最大值，考虑到答案可能很大，故只需要输出答案对 $10^9+7$ 取模后的值。 ### 输入格式 输入的第一行包括一个整数 $n$（$1\leqslant n\leqslant10^3$），表示棋盘的行数（也即列数）， 接下来的 $n$ 行，每行包括 $n$ 个字符：'0', '1', '2' 或者 '3'，表示这一行气球上面的数字。 ### 输出格式 输出可能得到的最大乘积对 $10^9+7$ 取模后的结果。 注意，你不需要保证最终得到的余数是最大的，而只需要计算出最大乘积对 $10^9+7$ 取模后的结果。