首页 > 其他分享 >迷宫逃脱

迷宫逃脱

时间:2023-11-15 19:22:41浏览次数:32  
标签:cn int ll 迷宫 long using 逃脱 define

链接:迷宫逃脱【算法赛】 - 蓝桥云课 (lanqiao.cn)

题意

 可以考虑记忆化搜索

本人代码只能通过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

 

标签:cn,int,ll,迷宫,long,using,逃脱,define
From: https://www.cnblogs.com/ZouYua/p/17834557.html

相关文章

  • 1112.迷宫
    dfs模板#include<iostream>#include<cstring>usingnamespacestd;constintN=105;charg[N][N];intk,n;boolvis[N][N];intsx,sy,ex,ey;intdx[]={-1,1,0,0};intdy[]={0,0,-1,1};voiddfs(intx,inty){vis[x][y]=1;......
  • 逃离迷宫
    你好,欢迎使用由do_it_tomorrow开发的小游戏,这个游戏仅限于课下娱乐,造成任何损失作者概不负责。如果对于游戏有任何问题或者建议,欢迎进行反馈。在游戏中,玩家将在迷宫中尝试逃离,但是会有各种的怪物伺机而动,只有三思而后行才能在考验重重的迷宫中成功逃生。本游戏支持存档,并且具有......
  • 【算法】万圣节前夕的迷宫挑战
    这一天阳光和煦,小悦将捣蛋的侄子小明送回家后,紧绷的神经终于得以放松。在过去的一周里,小悦以无比的耐心和细心照顾着小明,同时也不忘在编程的道路上引领他迈出第一步。万圣节前夕的一天,书房中的陈设在阳光下显得庄重而温暖,小悦正专心致志地处理着手头的工作。突然,一封邮件如不速之......
  • [SWPUCTF 2021 新生赛]老鼠走迷宫(详细版
    附件下载https://wwvc.lanzouj.com/iYLez1br84jg解题思路用pyinstxtrator解析exe重点:将无后缀的5先修改后缀为pyc,然后随便找一个pyc文件补齐5.pyc的前16位十六进制数值(这道题以struct.pyc为例)将.pyc反编译为.py找到maze,从而找到最短路径改后缀下载附件,拿到一个无后缀的......
  • 逆波兰表达式与迷宫算法
    中项表达式是人类的算术思路,逆波兰表达式是机器结合栈结构完成算式解析的最佳结构。文章链接:https://zhuanlan.zhihu.com/p/357982040迷宫算法文章链接:https://blog.csdn.net/m0_53157173/article/details/114486303......
  • 视频监控场景新花样——密室逃脱监控平台
    近日,《社会单位和重点场所消防安全管理规范第6部分:密室逃生场所》这一新标准在市市场监管局网站上公开征求意见。征求意见的新标准提出,密室逃生场所不应布置在地下二层及以下楼层,应设置场控室,场控室应对主题单元内每个房间进行全方位、无死角的监控,并能随时进行语音对讲。此外,场......
  • 题解 hdu 1269 迷宫城堡
    找点图论练习题写,发现hdu又寄了,那就发到blog里吧。思路:tarjan缩点判断DAG中点数是否为1。若是,则该图为强连通图。 //producedbymiya555//stupidmistakes:多测记得清空//ideas:tarjan模板#include<bits/stdc++.h>usingnamespacestd;constintN=10010;intn,m,low[......
  • 算法题 逃离迷宫
     题目描述:你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在......
  • 我的心理之旅:探索_MMPI_测验的迷宫
    引言人的心灵是一个奇妙而复杂的迷宫。有时候,我们甚至对自己也是个谜。这就是为什么心理学家们发明了各种工具来揭示我们的内心世界。明尼苏达多相人格调查表(MMPI)就是其中之一。在我最近的一次人格探索中,我决定深入了解MMPI,看看它能否为我揭示一些未知的真相。第一次邂逅MMPI......
  • 【LuoGu 1363】幻象迷宫——深度优先搜索 + 读题
    幻象迷宫题目背景(喵星人LHX和WD同心协力击退了汪星人的入侵,不幸的是,汪星人撤退之前给它们制造了一片幻象迷宫。)WD:呜呜,肿么办啊……LHX:momo...我们一定能走出去的!WD:嗯,+U+U!题目描述幻象迷宫可以认为是无限大的,不过它由若干个\(N\timesM\)的矩阵重复组成。矩阵中有的地......