立方体IV（暑假每日一题 10）

Vincenzo 决定制作立方体 IV，但所有预算只够制作一个正方形迷宫。

它是一个完美的迷宫，每个房间都呈正方形，并具有 $4$ 扇门（四个边一边 $1$ 个）。

每个房间里都有一个号码。

一个人只有在下一个房间的号码比当前房间的号码大 $1$ 的情况下，才能从当前房间移动到下一个房间。

现在，Vincenzo 为所有房间分配了唯一的号码（ $1,2,3,\dots S^2$）然后将 $S^2$ 个人放在了迷宫中，每个房间 $1$ 个，其中 $S$ 是迷宫的边长。

能够移动次数最多的人将获胜。

弄清楚谁将成为赢家，以及他将能够到达的房间数量。

输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组测试数据第一行包含整数 $S$，表示迷宫的边长。

接下来 $S$ 行，每行包含 $S$ 个整数，表示具体的迷宫的房间号分布，需注意 $1,2,3,\dots S^2$ 这 $S^2$ 个数字，每个数字只出现一次。

输出格式
每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: r d，其中 $x$ 是组别编号（从 $1$ 开始），$r$ 是获胜的人最初所在房间的房间号，$d$ 是他可以到达的房间数量。

如果有多个人可到达的房间数相同，那么最初所在房间的房间号最小的人将获胜。

数据范围
$1\le T\le 100,$
$1\le S\le 1000$
输入样例：

2
2
3 4
1 2 


3
1 2 9 
5 3 8 
4 6 7 
1
2
3
4
5
6
7
8
9
10

输出样例：

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

---

#include
#include

using namespace std;

const int N = 1010;

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

int get(int x, int y, int d){
    
    if(f[x][y] != -1) return f[x][y];
    int res = 0;
    for(int i = 0; i < 4; i++){
        
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1 && a <= s && b >= 1 && b <= s && g[a][b] == g[x][y] + 1){
            
            res = max(res, get(a, b, d + 1));
        }
    }
    
    return f[x][y] = res + 1;
}

int main(){
    
    int t;
    scanf("%d", &t);
    
    for(int k = 1; k <= t; k++){
        
        scanf("%d", &s);
        
        for(int i = 1; i <= s; i++)
            for(int j = 1; j <= s; j++)
                scanf("%d", &g[i][j]);
        memset(f, -1, sizeof f);
        int sd = -1, d = -1;
        
        for(int i = 1; i <= s; i++)
            for(int j = 1; j <= s; j++){
                int r = get(i, j, 1);
                if(r > d || r == d && sd > g[i][j]) sd = g[i][j], d = r;   
            }
        
        printf("Case #%d: %d %d\n", k, sd, d);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53