首页 > 其他分享 >暂存的题解

暂存的题解

时间:2024-11-06 18:57:41浏览次数:1  
标签:int 题解 cin yy xx 钥匙 暂存 op

P4011 孤岛营救问题

感觉其实我能想出来,但是对难题产生了恐惧,直接看题解了,确实简单,很抱歉浪费了一道题。

数据范围很小,搜索 bfs,钥匙直接状态压缩,找到答案立即返回,否则就无解。

我们要彻底的分析问题,为什么我想不到,以后我要怎么总结,首先看到题之后要先看数据范围,看到数据范围非常小就考虑搜索,其次我们看到我们需要钥匙所有我们状态肯定也要储存钥匙,但钥匙都储存空间有点大就考虑状态压缩,直接 dfs 就可以。

其实还可以有钥匙的建分层图跑最短路,但是就这样吧。

注:状压开大数组啊,为什么我没开大,唐。

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define re register 
const int N=5e5+10;
using namespace std;

int n,m,p;

int k;

int mp[15][15][15][15];
vector<int> mpkey[20][20];

struct ss{
	int x,y,a,sum;
}; 

queue<ss> q;

int xa[5]={0,0,1,-1};
int ya[5]={1,-1,0,0};

int vis[15][15][1<<15];

int solve(){
	
	q.push({1,1,0,0});
	
	while(!q.empty()){
		ss fir=q.front();
		q.pop();
		int x=fir.x,y=fir.y,z=fir.a,sum=fir.sum;
		
		if(x==n&&y==m){
			return sum;
		}
		for(int i=0;i<mpkey[x][y].size();i++){
			int jk=mpkey[x][y][i];
			z|=(1<<(jk-1));
		}	
		vis[x][y][z]=1;
		
		for(int i=0;i<4;i++){
			int xx=x+xa[i];
			int yy=y+ya[i];
			
			if(!(xx>=1&&xx<=n&&yy>=1&&yy<=m)||vis[xx][yy][z]==1){
				continue;
			}
			if(mp[x][y][xx][yy]==-1){
				continue;
			}
			if(mp[x][y][xx][yy]!=0){
				if(((z>>(mp[x][y][xx][yy]-1))&1)!=1){
					continue;
				}	
			}
			q.push({xx,yy,z,sum+1});
		}
	}
	return 0;
} 

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
	memset(vis,0,sizeof 0);
	cin>>n>>m>>p;
	
	cin>>k;
	
	for(int i=1;i<=k;i++){
		int x,y,xx,yy,op;
		cin>>x>>y>>xx>>yy>>op;
		if(op==0){
			op=-1;
		}
		mp[x][y][xx][yy]=op;
		mp[xx][yy][x][y]=op; 
	}
	
	cin>>k;
	
	for(int i=1;i<=k;i++){
		int x,y,op;
		cin>>x>>y>>op;
		mpkey[x][y].push_back(op);
	}
	int ans=solve();
	if(ans!=0){
		cout<<ans;
	}
	else{
		cout<<-1;
	}
	return 0;
}

标签:int,题解,cin,yy,xx,钥匙,暂存,op
From: https://www.cnblogs.com/sadlin/p/18530729

相关文章

  • [USACO22JAN] Minimizing Haybales P 题解
    [USACO22JAN]MinimizingHaybalesP随机化?五分。显然对于任意\(a_i,a_j\),若\(|a_i-a_j|>K\),则这两堆草的先后顺序永远不会改变。所以易得暴力:对于所有这样的\(i,j\),不妨设\(i<j\),则连一条\(i\toj\)的边,答案就是这个图字典序最小的拓扑排序,优先队列即可。voidtoposort(......
  • [USACO21DEC] Tickets P 题解
    [USACO21DEC]TicketsP首先我们思考暴力的\(O(n^2)\)怎么做。显然比起每次以\(i\)为起点跑\(n\)遍最短路,建反图后分别以\(1\)和\(n\)为起点跑两遍最短路是更加经济的方式。然后你可能会以为\(\text{dis}(1,i)+\text{dis}(n,i)\)就是答案了,之后你就会发现连样例都过......
  • 【问题解决】java.lang.SecurityException: JCE cannot authenticate the provider BC
    问题复现历史项目升级JDK(由1.7升级到8),进行加密/解密时出现报错java.lang.SecurityException:JCEcannotauthenticatetheproviderBC。问题原因Wikipa上查到JCE的描述如下:JavaCryptographyExtension(JCE)isanofficiallyreleasedStandardExtensiontotheJavaPl......
  • 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间
    问题复现项目上历史项目为解决漏洞扫描从Tomcat6.0升级到了9.0版本,服务启动的日志显示如下警告,数据源是通过JNDI方式在server.xml中配置的,控制台上狂刷无法找到表空间的错误(没截图)报错:06-Nov-202410:32:03.701警告[main]java.util.ArrayList.forEachName=数据源Proper......
  • CF1909题解
    CF1909A一眼秒之题,我们发现就是四个方向选三个方向,若是存在一个点它的方向恰好在(0,0)点的另外一个方向,则一定不成立枚举4个方向,发现有点在这个方向,显然选除这个点之外的三个方向的方案就不可行点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=105;int......
  • 题解:P7082 [NWRRC2013] Dwarf Tower
    涉及知识点:动态规划。解题思路设\(dp_i\)为得到\(i\)最小的花费。可以得到转移方程:\(dp_{a_i}=\min(dp_{x_i}+dp_{y_i},dp_{a_i})\)。很明显最多迭代\(n\)次,还需要再外面套一个循化即可。但是有些OJ没有洛谷跑得快,所以需要加一点优化。如果当前循环没有更新......
  • 【题解】CF1956
    CF1956A简要题意有\(n\)个人玩一个游戏,把这\(n\)个人分别编号为\(1\)到\(n\)。每一轮,编号为\(a_1,a_2,\ldots,a_k\)(\(a\)序列递增)的人会被踢出这个游戏,剩下的人会补齐空位并重新从\(1\)开始编号。当某一轮没有人被踢出时,游戏结束,剩下没有被踢出的人成为......
  • “SSL 证书验证失败”问题解决方法“urllib.error.URLError: <urlopen error [SSL: CER
    第一部分:问题描述第二部分:解决方法错误的代码:dataset_train=datasets.MNIST('../data/mnist/',train=True,download=True,transform=trans_mnist)dataset_test=datasets.MNIST('../data/mnist/',train=False,download=True,transform=trans......
  • P6667 [清华集训2016] 如何优雅地求和 题解
    一道非常有启发性的题目。思路考虑对于一个给出点值的多项式函数如何处理。我们发现,对于一个\(m\)次多项式\(f(x)\),由于\(\binom{x}{i}\)为\(i\)次多项式,所以说我们必定可以把一个多项式函数写成如下模样:\[F(k)=\sum_{i=0}^m\binom{k}{i}f_i\]可以看出,\(f_i\)实际上......
  • CSP-J2024题解
    T1扑克牌本题要求:在给定的扑克牌的基础上,还需要多少张牌可以让扑克牌凑成一整套,试题中读入的字符串每个都代表一张合法的扑克牌。可以使用C++STL中的set(集合)完成本题。这是因为,set可以自动去重,去除重复的牌(字符串)后,剩下的字符串就是实际拥有的不同的牌。而一副扑克牌有......