题目描述

美丽的小阳

Vincenzo 决定制作立方体 IV，但所有预算只够制作一个正方形迷宫。
它是一个完美的迷宫，每个房间都呈正方形，并具有 4扇门（四个边一边 1个）。
每个房间里都有一个号码。一个人只有在下一个房间的号码比当前房间的号码大 1的情况下，才能从当前房间移动到下一个房间。
现在，Vincenzo 为所有房间分配了唯一的号码（1,2,3,…S2）然后将 S2 个人放在了迷宫中，每个房间 1 个，其中 S是迷宫的边长。
能够移动次数最多的人将获胜。弄清楚谁将成为赢家，以及他将能够到达的房间数量。
输入格式：第一行包含整数 T，表示共有 T组测试数据。

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

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

输出格式：
每组数据输出一个结果，每个结果占一行。
结果表示为 Case #x: r d，其中 x是组别编号（从 1 开始），r 是获胜的人最初所在房间的房间号，d是他可以到达的房间数量。
如果有多个人可到达的房间数相同，那么最初所在房间的房间号最小的人将获胜。

样例

输入样例：

2
2
3 4
1 2 


3
1 2 9 
5 3 8 
4 6 7 

输出样例：

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

算法1

(记忆化DP+DFS搜索) $O(n^2)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 220;
int ans = 0;
pair<int,int>place;
int d[][2] = {0,1,-1,0,1,0,0,-1};
int t,n;
int mp[N][N],f[N][N],mm[N][N],mem[N][N];
int dfs(int x,int y){
    if(f[x][y]!=1) return f[x][y];
    mm[x][y] = 1;
    for(int i = 0;i<4;i++){
        int tx = x + d[i][0],ty = y+d[i][1];
        if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&mp[tx][ty]-mp[x][y]==1&&mm[tx][ty]==0){
            f[x][y] = max(f[x][y],dfs(tx,ty)+1);
        }
    }
    mm[x][y] = 0;
    return f[x][y];
}
signed main(){
        int times = 1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++) {
            cin >> mp[i][j];
            mem[i][j] = mp[i][j];
            f[i][j] = 1;
        }

        for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++){
            int tt = dfs(i,j);
            if(tt>ans){
                ans = tt;
                place = {i,j};
            }else if(tt==ans&&mem[place.first][place.second]>mem[i][j]){
                ans = tt;
                place = {i,j};
            }
        }
        cout << "Case #"<<times++<<": ";
        cout << mem[place.first][place.second] <<" "<<ans <<endl;
        ans = 0;
    }

}