Aizu 2538 Stack Maze【记忆化搜索】

2024-08-24 11:38
文章标签 搜索 stack 记忆 aizu maze 2538

本文主要是介绍Aizu 2538 Stack Maze【记忆化搜索】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

其实我并不知道我的姿势算是什么。
一开始想着用二维的记忆化搜索,用 dp[x][y] 表示 (x,y)(H,W) 能够得到的最大happy值。但是很遗憾的是,这样没法记录,在前进的路上,我有多少个宝石、能够经过多少宝石洞。
所以就想着如何记录,最后发现难以记录。如果是这样的记忆化搜索,时间复杂度大约是 O(n2) ,那么就想着可以进行扩大时间复杂度的算法。大约估算了一下 504=6250000 ,可以做。
于是最终想到了记录起点和终点的方法。
用类似与区间dp的方式来计算。
记录每一种洞的位置,或者记录每个宝石可以填到那些洞里,那么就可以将区间分成 (1,1)(xx,yy)(x,y)(H,W) ,其中 (xx,yy) 为宝石的所在地, (x,y) 为宝石洞的所在地。如果成功走过去了就可以将区间答案+1。
注意一下如果区间 {l⃗ ,r⃗ } 的特判情况,如果 l⃗ r⃗  则返回0,如果 l⃗ r⃗  l⃗  不可到达 r⃗  则返回

//      whn6325689
//      Mr.Phoebe
//      http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<50
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define ls (idx<<1)
#define rs (idx<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int dir[2][2] = {1,0,0,1};
char ma[55][55];
int dp[55][55][55][55];
int g[55][55][55][55];
int h,w;
vector<pii> hole[26];bool in(int x,int y)
{return x>=1 && x<=h && y>=1 && y<=w && ma[x][y]!='#';
}int dfs(int px,int py,int x,int y)
{if(~dp[px][py][x][y])   return dp[px][py][x][y];if(x<px || y<py)    return dp[px][py][x][y]=0;if(x==px && y==py)  return dp[px][py][x][y]=0;if(!g[px][py][x][y])    return dp[px][py][x][y]=-INF;int ret=0;if(ma[px][py]>='a' && ma[px][py]<='z'){int je=ma[px][py]-'a';for(int k=0; k<hole[je].size(); k++){int nx=hole[je][k].first;int ny=hole[je][k].second;if(px<=nx && py<=ny && nx<=x && ny<=y && g[px][py][nx][ny] && g[nx][ny][x][y]){for(int i=0; i<2; i++){int xx=px+dir[i][0];int yy=py+dir[i][1];if(in(xx,yy)){if(in(nx-1,ny))ret=max(ret,dfs(xx,yy,nx-1,ny)+1+dfs(nx,ny,x,y));if(in(nx,ny))ret=max(ret,dfs(xx,yy,nx,ny-1)+1+dfs(nx,ny,x,y));}}}}}for(int i=0; i<2; i++){int xx=px+dir[i][0];int yy=py+dir[i][1];if(in(xx,yy) && g[xx][yy][x][y])ret=max(ret,dfs(xx,yy,x,y));}return dp[px][py][x][y]=ret;
}void init()
{CLR(dp,-1);CLR(g,0);for(int i=0; i<26; i++)hole[i].clear();
}int main()
{
freopen("data.txt","r",stdin);while(read(h)&&read(w)&&(w+h)){init();for(int i=1; i<=h; i++){scanf("%s",ma[i]+1);for(int j=1; j<=w; j++)if(ma[i][j]<='Z' && ma[i][j]>='A')hole[ma[i][j]-'A'].pb(mp(i,j));}for(int i=h; i>=0; i--)for(int j=w; j>=0; j--){if(ma[i][j]=='#')   continue;for(int k=0; k<2; k++){int xx=i+dir[k][0];int yy=j+dir[k][1];if(!in(xx,yy))  continue;for(int x=xx; x<=h; x++)for(int y=yy; y<=w; y++)g[i][j][x][y]|=g[xx][yy][x][y];}g[i][j][i][j]=1;}int ans=dfs(1,1,h,w);if(ans==-INF)printf("%d\n",-1);elseprintf("%d\n",ans);}return 0;
}

这篇关于Aizu 2538 Stack Maze【记忆化搜索】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102380

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

【python计算机视觉编程——7.图像搜索】

python计算机视觉编程——7.图像搜索 7.图像搜索7.1 基于内容的图像检索(CBIR)从文本挖掘中获取灵感——矢量空间模型(BOW表示模型)7.2 视觉单词**思想****特征提取**: 创建词汇7.3 图像索引7.3.1 建立数据库7.3.2 添加图像 7.4 在数据库中搜索图像7.4.1 利用索引获取获选图像7.4.2 用一幅图像进行查询7.4.3 确定对比基准并绘制结果 7.

JS中【记忆函数】内容详解与应用

在 JavaScript 中,记忆函数(Memoization)是一种优化技术,旨在通过存储函数的调用结果,避免重复计算以提高性能。它非常适用于纯函数(同样的输入总是产生同样的输出),特别是在需要大量重复计算的场景中。为了彻底理解 JavaScript 中的记忆函数,本文将从其原理、实现方式、应用场景及优化方法等多个方面详细讨论。 一、记忆函数的基本原理 记忆化是一种缓存策略,主要用于函数式编

记忆化搜索【下】

375. 猜数字大小II 题目分析 题目链接:375. 猜数字大小 II - 力扣(LeetCode) 题目比较长,大致意思就是给一个数,比如说10,定的数字是7,让我们在[1, 10]这个区间猜。 如果猜大或猜小都会说明是大了还是小了,此外,我们还需要支付猜错数字对应的现金。 现在就是让我们定制一个猜测策略,确保准备最少的钱能猜对 如果采用二分查找,只能确保最小次数,题目要求的