Powered by:NEFU AB-IN

Link

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;
  }