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