Fence
Mr. Dokmai is a flower planter. He plants rare flowers of high values in a rectangular land plot divided into sections of M rows by N columns. He had many theft problems, so he built fences to protect his flowers from thieves. Since flowers have different values, some sections are better protected.
Unfortunately, his fences cannot stand the test of time and some fences were destroyed due to their age. To evaluate the current situation, Mr. Dokmai draws a map and associates a number to each land section. In his map, one means that the section is fence, while zero means that the section has no fence and is suitable for planting.Figure 1 illustrates an example of a map of 11 rows by 12 columns.
Figure 1. Illustration of land plot for flower planting.
A thief can enter the land plot at any outermost section (highlighted in Figure 1). However, if the section has a fence, it means that the thief must cut through the fence to enter. Once the thief enters the land plot, he may need to cut through more fences to get into a certain section. It can take a lot of time and effort if several fences are to be cut.
Assume that the thief can move from one section to another that is adjacent to it in horizontal or vertical directions, but not diagonal ones. For example, if he is in a section at Row 5 Column 7. He can move to sections at Row 4 Column 7, or Row 6 Column 7, or Row 5 Column 6, or Row 5 Column 8. However, he cannot move to section at Row 4 Column 6, for example.
Assume further that the security level of a section is the minimum number of fence cutting that a thief needs to enter the section. For instance, the security level of section at Row 6 Column 6 is 2, that of section at Row 4 Column5 is 1, that of section at Row 1 Column 3 is 0. It is important to note that the row and column indices start at 1.
Mr. Dokmai now needs to plant very expensive flowers, so he is looking for the most secure sections. He also wants to know the number of sections with highest security level. Note that only sections represented by 0 in the map are suitable for flower planting. Mr. Dokmai has no intention to remove any fence to create a new section for flower planting.
Your task is to write a program that determines the highest security level and the number of sections having the highest security level.
Input
First line of input is a number of test cases T ≤ 10. Note that integers in the same line are separated by one white space.
The first line of a test case has two integers R and C (5 ≤ R, C ≤ 1000). The first integer is the number of rows R and second is the number of columns C of the map sections.
Lines 2 to R+1 contain section data of each row, from Row 1 to Row R, respectively. Each line has C integers where0 represents a section suitable for flower planting and 1 represents a fence.
Note: the map always has at least one section suitable for flower planting. Also, if you are using Java programming language, it is recommended that you use BufferedReader and StreamTokenizer to read input data.
Output
For each test case, display 2 integers. The first is a non-negative integer showing the highest security level of a land section suitable for flower planting. The second is the number of sections having the highest security level. The two numbers are separated by one white space.
Explanation: For both examples, the stars below represent the section with the highest security level. The thick underlined numbers represent some of the paths that a thief can go into the highest security section passing smallest number of fence.