8436:Saving Tang Monk
题解
- 非常多的条件，但题目很有启发性
- 可以看作高维状态的在最短路径
- 这样想来之前格子类型的问题，本质是将坐标看作状态节点
- 很久以前的关于转折段数问题，也可以为段数增加状态，也可以用trick做
code
//状态压缩+高维bfs
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define ll long long
#define ull unsigned long long
#define name2str(name) (#name)
#define db(x) cout<<#x"=["<<(x)<<"]"<<endl
#define CL(a,b) memset(a,b,sizeof(a))
#define sf(a) scanf("%d",&a)
#define pr(a) printf("%d
",a)
#define rng(a) a.begin(),a.end()
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fr0(i,m) for(int i=0;i<m;i++)
#define fr1(i,m) for(int i=1;i<=m;i++)
//author:fridayfang
//date:19 3月 15
const double esp=1e-8;
const int mod=1e9+7;
const double pi=acos(-1);
const int inf=0x3f3f3f3f;
const int maxn = 1e6 + 5;
const int maxm = 1e6+5;
int vis[110][100][10][40];//mpp[i][j][k][s]
//拿到k把钥匙,杀死s状态的蛇，到达i,j的状态标记
char mp[110][110];
struct node{
int x,y,k,s,t;
node(){}
node(int _x,int _y,int _k,int _s,int _t):x(_x),y(_y),k(_k),s(_s),t(_t){}
bool friend operator <(node n1,node n2){
return n1.t>n2.t;
}
};
int mv[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct pos{
int x,y;
}ps[5];//记录蛇的位置
void show(node no){
printf("(x,y)=(%d %d),keys=%d t=%d ",no.x,no.y,no.k,no.t);
vector<int> tmp;int t=no.s;
while(t){
if(t&1)printf("1");
else printf("0");
t=t>>1;
}
printf("
");
}
int N,M;//k==M
int sx,sy,dx,dy;
int bfs(){
priority_queue<node> pq;pq.push(node(sx,sy,0,0,0));
vis[sx][sy][0][0]=1;
while(!pq.empty()){
node tmp=pq.top();pq.pop();
int cx=tmp.x,cy=tmp.y,ck=tmp.k,cs=tmp.s,ct=tmp.t;
if((ck==M)&&(cx==dx)&&(cy==dy))return ct;
for(int i=0;i<4;i++){
int nx=cx+mv[i][0],ny=cy+mv[i][1],nk=ck,ns=cs,nt=ct+1;
if((nx<0)||(nx>=N)||(ny<0)||(ny>=N)||(mp[nx][ny]=='#')){
continue;
}
if(mp[nx][ny]=='S'){
int tt=-1;
for(int t=0;t<5;t++){
if((ps[t].x==nx)&&(ps[t].y==ny)){tt=t;break;}
}
if(cs&(1<<tt)){//already killed
//nothing change
}
else{
nt=ct+2;(ns=cs|(1<<tt));
}
}
if(mp[nx][ny]>='1'&&mp[nx][ny]<=('0'+M)){//get key
int keyn=mp[nx][ny]-'0';
if(keyn==(ck+1))nk=ck+1;
}
if(!vis[nx][ny][nk][ns]){
vis[nx][ny][nk][ns]=1;
pq.push(node(nx,ny,nk,ns,nt));
}
}
}
return -1;
}
int main(){
while(scanf("%d %d",&N,&M)&&N){
int scnt=0;CL(vis,0);
for(int i=0;i<N;i++){
scanf("%s",mp[i]);
for(int j=0;j<N;j++){
if(mp[i][j]=='K'){sx=i,sy=j;}
else if(mp[i][j]=='T'){dx=i,dy=j;}
else if(mp[i][j]=='S'){ps[scnt].x=i,ps[scnt].y=j,scnt++;}
}
}
int ans=bfs();
if(ans!=-1)pr(ans);
else printf("impossible
");
}
return 0;
}
2152:Pots
code
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define ll long long
#define ull unsigned long long
#define name2str(name) (#name)
#define db(x) cout<<#x"=["<<(x)<<"]"<<endl
#define CL(a,b) memset(a,b,sizeof(a))
#define sf(a) scanf("%d",&a)
#define pr(a) printf("%d
",a)
#define rng(a) a.begin(),a.end()
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fr0(i,m) for(int i=0;i<m;i++)
#define fr1(i,m) for(int i=1;i<=m;i++)
//author:fridayfang
//date:19 3月 15
const double esp=1e-8;
const int mod=1e9+7;
const double pi=acos(-1);
const int inf=0x3f3f3f3f;
const int maxn = 1e6 + 5;
const int maxm = 1e6+5;
int A,B,C;
struct state{
int a,b,s;
state(){}
state(int _a,int _b,int _s):a(_a),b(_b),s(_s){}
};
int get_val(state s){
return (s.a*101)+s.b;
}
int vis[11000];
state mv(state old,int op){
int a=old.a,b=old.b,s=old.s;
if(op==0){a=A;}
else if(op==1){b=B;}
else if(op==2){a=0;}
else if(op==3){b=0;}
else if(op==4){
if(a<(B-b)){b+=a;a=0;}
else {a=a-(B-b);b=B;}
}
else if(op==5){
if(b<(A-a)){a+=b;b=0;}
else {b=b-(A-a);a=A;}
}
return state(a,b,s+1);
}
void show(state cur){
printf("[a]=%d [b]=%d [s]=%d
",cur.a,cur.b,cur.s);
}
int path[200][200];
int pre[40000];
int ops[40000];
int endv;
int bfs(){
state begin=state(0,0,0);
//show(begin);
queue<state> q;q.push(begin);
int val=get_val(begin);vis[val]=1;
while(!q.empty()){
state os=q.front();q.pop();
//printf("pop
");show(os);
int cval=get_val(os);
int x=os.a,y=os.b;
if((x==C)||(y==C)){endv=cval;return os.s;}
for(int i=0;i<6;i++){
state ns=mv(os,i);
//printf("extend
");show(ns);
int nval=get_val(ns);
if(!vis[nval]){
vis[nval]=1;
pre[nval]=cval;
ops[nval]=i;
q.push(ns);
}
}
}
return -1;
}
void decode(int op){
if(op==0){printf("FILL(1)
");}
if(op==1)printf("FILL(2)
");
if(op==2)printf("DROP(1)
");
if(op==3)printf("DROP(2)
");
if(op==4)printf("POUR(1,2)
");
if(op==5)printf("POUR(2,1)
");
}
int main(){
scanf("%d %d %d",&A,&B,&C);
CL(vis,0),CL(ops,-1),CL(pre,-1);
int ans=bfs();
if(ans!=-1){
pr(ans);
int cur=endv;
vector<int> v;
while(cur!=-1){
int op=ops[cur];v.push_back(op);
//decode(op);
cur=pre[cur];
}
for(int i=v.size()-1;i>=0;i--){
decode(v[i]);
}
}
else{
printf("impossible
");
}
return 0;
}