题目描述
If we need to be prepared for the possible danger of an alien invasion, the first thing to do is tofind out where can they come from. One way to determine if a planet is inhabited by intelligentcreatures is to study high resolution pictures of planets trying to find typical characteristics ofeffects of an intelligent life. There are so many habitable planets that a computer program mustbe written for this task. One distinctive feature of a colonized planets is the presence of surfacemines. An alien mine is a square structure with a depth uniformly decreasing from one of thesides of the square towards the opposite.
Your task is to find the largest mine on a provided bitmap image of a planet. The picture isa rectangular grid of numbers between 0 and 65535, representing the shades of grey. Mineswill appear as squares of either the same shade or with shade levels gradually and uniformlychanging from one side to another. See the above figure for an example. Your program willconsider only square mines in some special orientations.An axis-parallel square is the set of pixels (i, j) such that c1 ≤ i ≤ c2 and r1 ≤ j ≤ r2 for some c1, c2, r1, r2, c2 - c1 = r2 - r1.A vertically (horizontally) oriented mine is an axis-parallel square for which there exist integersS and K such that the shade of every pixel (i, j) of the square is equal to S + iK (S + jK forhorizontally oriented mines).A diagonally oriented mine is an axis-parallel square for which there exist integers Q ∈ {1, -1},S and K such that the shade of every pixel (i, j) of the square is equal to S + (i + Qj)K .
Your task is to find the largest mine on a provided bitmap image of a planet. The picture isa rectangular grid of numbers between 0 and 65535, representing the shades of grey. Mineswill appear as squares of either the same shade or with shade levels gradually and uniformlychanging from one side to another. See the above figure for an example. Your program willconsider only square mines in some special orientations.An axis-parallel square is the set of pixels (i, j) such that c1 ≤ i ≤ c2 and r1 ≤ j ≤ r2 for some c1, c2, r1, r2, c2 - c1 = r2 - r1.A vertically (horizontally) oriented mine is an axis-parallel square for which there exist integersS and K such that the shade of every pixel (i, j) of the square is equal to S + iK (S + jK forhorizontally oriented mines).A diagonally oriented mine is an axis-parallel square for which there exist integers Q ∈ {1, -1},S and K such that the shade of every pixel (i, j) of the square is equal to S + (i + Qj)K . 输入
The input contains several descriptions of pictures. The first line of each description containstwo numbers N and M (1 ≤ N, M ≤ 2000), the height and width of the picture. The followingN lines contain M space-separated integers each -- there is at least one space character betweennumbers but there may be more spaces and also additional spaces at the beginning or end of theline are allowed. The j-th number in the i-th row Ai,j (0 ≤ Ai,j ≤ 65535) describes the shadeof grey of the pixel in the ith row and jth column of the picture bitmap.The last description is followed by a line containing two zeros
输出
For each picture, output the area (number of pixels inside) of the largest horizontal, vertical, ordiagonal mine
样例输入 Copy
4 4
10 1 13 20
18 9 11 13
5 7 9 6
6 5 7 7
3 3
10 1 13
18 9 11
5 1000 9
4 4
10 12 15 20
5 9 13 10
5 9 13 6
5 9 13 7
0 0
样例输出 Copy
4
1
9