691. Cube IV

Vincenzo Decided to make a cube IV, But all the budget is only enough to make a square maze .

It is a perfect maze , Each room is square , And 4 door （ Four sides, one side 1 individual ）.

There is a number in every room .

A person's number in the next room is only larger than the number in the current room 1 Under the circumstances , To move from the current room to the next room .

Now? ,Vincenzo All rooms are assigned a unique number （1,2,3,…S2） And then S2 I put myself in the maze , Every room 1 individual , among S Is the side length of the maze .

The person who can move the most times will win .

Figure out who will win , And the number of rooms he will be able to reach .

Input format

The first line contains integers T, Expressing common ownership T Group test data .

The first row of each set of test data contains integers S, Represents the side length of the maze .

Next S That's ok , Each row contains S It's an integer , Represents the room number distribution of the specific maze , Attention should be paid to 1,2,3,…S2 this S2 A digital , Each number appears only once .

Output format

Each group of data outputs a result , Each result takes up one line .

The result is expressed as Case #x: r d, among x It's the group number （ from 1 Start ）,r Is the room number of the winner's original room ,d Is the number of rooms he can reach .

If more than one person can reach the same number of rooms , Then the person with the smallest room number in the original room will win .

Data range

1≤T≤100,
1≤S≤1000

sample input ：

2
2
3 4
1 2 


3
1 2 9 
5 3 8 
4 6 7

sample output ：

Case #1: 1 2
Case #2: 6 4

Code ：

//  Memory search 
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, g[N][N], f[N][N];
int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

int dfs(int x, int y)
{
    
    int &v = f[x][y];
    if (v != -1)
        return v;

    v = 1;
    for (int i = 0; i < 4; i++)
    {
    
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < n && g[a][b] == g[x][y] + 1)
            v = max(v, dfs(a, b) + 1);
    }

    return v;
}

int main()
{
    
    int T;
    cin >> T;
    for (int k = 1; k <= T; k++)
    {
    
        cin >> n;
        for (int i = 0; i < n; i++)
        {
    
            for (int j = 0; j < n; j++)
                cin >> g[i][j];
        }
        memset(f, -1, sizeof f);

        int id, cnt = 0;
        for (int i = 0; i < n; i++)
        {
    
            for (int j = 0; j < n; j++)
            {
    
                int t = dfs(i, j);
                if (t > cnt || t == cnt && id > g[i][j])
                {
    
                    cnt = t;
                    id = g[i][j];
                }
            }
        }
        printf("Case #%d: %d %d\n", k, id, cnt);
    }

    return 0;
}