摘要
Title: 691. 立方体IV
Tag: 记忆化搜索
Memory Limit: 64 MB
Time Limit: 1000 ms

691. 立方体IV

题意

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

记忆化搜索板子题

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-08-04 15:03:57
* @FilePath: \Acwing\691\691.cpp
* @LastEditTime: 2022-08-04 15:56:20
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int INF = INT_MAX;
const int N = 1e6 + 10;

void solve(int T)
{

    int n;
    cin >> n;

    vector<vector<int>> g(n + 10, vector<int>(n + 10)), f(n + 10, vector<int>(n + 10, -1));

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin >> g[i][j];
        }
    }

    int d = 0, r = n * n;
    
    function<int(int, int)> dp = [&](int x, int y) {
        if (f[x][y] != -1)
            return f[x][y]; // 如果遍历到了直接返回

        f[x][y] = 1; // 初始化走一步

        vector<PII> dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

        for (int i = 0; i < 4; ++i)
        {
            int xx = x + dir[i].first;
            int yy = y + dir[i].second;

            if (xx >= 1 && x <= n && yy >= 1 && yy <= n && g[xx][yy] == g[x][y] + 1)
            {
                f[x][y] = max(f[x][y], dp(xx, yy) + 1);
            }
        }

        return f[x][y];
    };

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            int step = dp(i, j);
            if (step > d || (step == d && g[i][j] < r))
            {
                d = step;
                r = g[i][j];
            }
        }
    }

    printf("Case #%lld: %lld %lld\n", T, r, d);
    return;
}

signed main()
{
    IOS;
    int T;
    cin >> T;
    for (int i = 1; i <= T; ++i)
    {
        solve(i);
    }
    return 0;
}

691. 立方体IV

题意

思路

代码