本文主要是介绍BOJ 4228 哈哈哈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：这题一看就知道要用状态压缩，本题和HDU 1429 胜利大逃亡（续）差不多。
解题思路：你可以把宝物压缩为二进制，例如：01001 代表你已经拿过 1 号和 4 号宝物了 0 代表相应的宝物没拿。用同样的方法把拿某个物品的前提条件也映射成二进制。假如你现在遇到 3 号宝物，如果3号宝物的前提条件是拿到 1 号 和 4 号宝物才能拿 3 号，那么前提条件可以用二进制表示为 ：01001 那么只要将这个二进制与你当前的 key 相与如果结果还是等于前提条件的二进制，表示前提条件已经满足。so 3 号物品可以取走（前提是没取过三号物品），否则不可以。
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
#define lld long long int
const double PI = 3.1415926 ;
const double INF = 99999999 ;
const int MX =25 ;
int n,m,mx ;
char s[MX][MX] ;
int b[MX] ;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ;
bool vis[MX][MX][MX] ;// 标记数组
struct node
{int x,y,key,step ;
} ;
bool search(int x,int y) // 判断是否出界
{if(x<0||y<0||x>=n||y>=m||s[x][y]=='#')return false ;return true ;
}
int bfs(int x,int y)
{int key,sx,sy,temp ;memset(vis,false,sizeof(vis)) ;queue<node>q ;node curt,next ;curt.x=x ;curt.y=y ;curt.key=0 ;curt.step=0 ;vis[x][y][0]=true ;q.push(curt) ;while(!q.empty()){curt=q.front() ;q.pop() ;if(curt.key==(1<<mx)-1&&s[curt.x][curt.y]=='E')return curt.step ;for(int i=0 ;i<4 ;i++){next.x=sx=curt.x+dx[i] ;next.y=sy=curt.y+dy[i] ;next.step=curt.step+1 ;next.key=key=curt.key ;if(search(sx,sy)) // 判断是否出界{if(s[sx][sy]>='0'&&s[sx][sy]<='9') // 是宝藏{temp=s[sx][sy]-'0' ;if(key&(1<<temp)) // 已经取过{if(!vis[sx][sy][key]){vis[sx][sy][key]=true ;next.key=key ;q.push(next) ;}}else // 还没取过{temp=s[sx][sy]-'0' ;if((key&b[temp])==b[temp])// 取该宝物的前提条件已经满足{next.key=key|(1<<temp) ;vis[sx][sy][next.key]=true ;q.push(next) ;}else if(!vis[sx][sy][key])// 前提条件没满足{vis[sx][sy][key]=true ;next.key=key ;q.push(next) ;}}}else if(!vis[sx][sy][key])// 不是宝藏{next.key=key ;vis[sx][sy][key]=true ;q.push(next) ;}}}}return -1 ;
}
int main()
{int sx,sy ;while(~scanf("%d%d",&n,&m)){for(int i=0 ;i<n ;i++){scanf("%s",s[i]) ;for(int j=0 ;j<m ;j++)if(s[i][j]=='S'){sx=i ;sy=j ;}else if(s[i][j]>='0'&&s[i][j]<='9')mx++ ;}int nx,ans=0,y ;for(int i=0 ;i<mx ;i++){scanf("%d",&nx) ;ans=0 ;for(int j=0 ;j<nx ;j++){scanf("%d",&y) ;ans=ans|(1<<y) ;}b[i]=ans ;// 取第 i 个宝物的前提条件}int an=bfs(sx,sy) ;if(an!=-1)printf("%d\n",an) ;else printf("Impossible\n") ;}return 0 ;
}
这篇关于BOJ 4228 哈哈哈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
