迷宫逃脱-526互联

题意

可以考虑记忆化搜索

本人代码只能通过75%样例，写的很乱，一眼丁真鉴定为依托答辩，代码贴最后了，先附上ac代码

#include<bits/stdc++.h>

using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define endl "\n"
#define int long long
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0)
const int N=1e3+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int n, m, q;
ll g[N][N];
ll mem[N][N][5];//5把钥匙的可以获得的最大值 
int dx[] = {1, 0};
int dy[] = {0, 1};
bool check(int x, int y)
{
  if(x <= n && y <= m) return true;
  return false;
}
ll dfs(int x, int y, int k)
{
  if(k < 0) return -1e18;
  if(x == n && y == m) return g[x][y];
  if(mem[x][y][k] != -1e18) return mem[x][y][k];
  for(int i = 0; i < 2; i ++)
  {
    int xx = x + dx[i], yy = y + dy[i];
    if(!check(xx, yy)) continue;
    if(__gcd(g[x][y], g[xx][yy]) == 1)
    {
      mem[x][y][k] = max(mem[x][y][k], dfs(xx, yy, k - 1) + g[x][y]);
    }
    else 
      mem[x][y][k] = max(mem[x][y][k], dfs(xx, yy, k) + g[x][y]);
  }
  return mem[x][y][k];
}
signed main()
{
    IOS;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i ++)
    {
      for(int j = 1; j <= m; j ++)
      {
        cin >> g[i][j];
        for(int k = 0; k <= q; k ++)
        {
          mem[i][j][k] = -1e18;
        }
      }
    }
    ll res = dfs(1, 1, q);
    if(res > 0) cout << res;
    else cout << -1;
    return 0;
}

答辩代码

#include<bits/stdc++.h>

using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define endl "\n"
#define int long long
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0)
const int N=1e3+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int n, m, q;
ll g[N][N];
ll dp[N][N][5];//5把钥匙的可以获得的最大值 

bool check(int x, int y, int cn)
{
  if(x <= n && y <= m && cn >= 0) return true;
  return false;
}
ll dfs(int x, int y, int cn)
{
  //ll p = g[i][j];
  if(dp[x][y][cn] != -1) return dp[x][y][cn];
  dp[x][y][cn] = 0;
  ll &t = dp[x][y][cn];
  if(check(x + 1, y, cn - 1) && __gcd(g[x + 1][y], g[x][y]) == 1) 
  {
    t = max(t, dfs(x + 1, y, cn - 1));
  }
  if(check(x, y + 1, cn - 1) && __gcd(g[x][y + 1], g[x][y]) == 1) 
  {
     t = max(t, dfs(x, y + 1, cn - 1));
  }

    if(check(x + 1, y, cn) && __gcd(g[x + 1][y], g[x][y]) > 1 )
    {
      t = max(t, dfs(x + 1, y, cn));
    }
    if(check(x, y + 1, cn) && __gcd(g[x][y + 1], g[x][y]) > 1)
    {
      t = max(t, dfs(x, y + 1, cn));
    }

  //cout << x << ' ' << y << ' ' << t << endl;
  return  dp[x][y][cn] = t + g[x][y];
}
signed main()
{
  IOS;
    cin >> n >> m >> q;
  for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= m; j ++)
       cin >> g[i][j];
  for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= m; j ++)
       for(int k = 0; k <= q; k ++)
        {
          dp[i][j][k] = -1;
        }
  dfs(1, 1, q);      
  ll res = -1;
  for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= m; j ++)
       for(int k = 0; k <= q; k ++)
        res = max(res, dp[i][j][k]);
  
  cout << res << endl;
    return 0;
}

View Code