http://acm.hdu.edu.cn/showproblem.php?pid=1429
终于开始能够做状态压缩的题了,虽然这只是状态压缩里面一道很简单的题.
状态压缩就是用二进制的思想来表示状态.
总共有10种钥匙,那么开一个(1<<10 的数组) 那么每次遇到一把钥匙我就用当前状态 | 钥匙转化为2进制的数值,然后遇到门的时候判断是否有对应的钥匙,只要用当前状态 & 门转化为2进制的值就可以。初始为0时,state=0,表示10个状态位都是0.那么每次遇到钥匙就改变相应的状态位。
比如当前state ==0 遇到 'a' 那么 state | 0 ==1 (1),遇上 'b'那么state | 1 ==3 (11)
这样每遇到一把钥匙,当前状态对应的位就变成1.
其余的就跟普通bfs没什么两样了。
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <string> #include <algorithm> #include <string> #include <set> #include <functional> #include <numeric> #include <sstream> #include <stack> #include <map> #include <queue> #pragma comment(linker, "/STACK:102400000,102400000") #define CL(arr, val) memset(arr, val, sizeof(arr)) #define ll long long #define inf 0x7f7f7f7f #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) (x) < (y) ? (x) : (y) #define Max(x, y) (x) < (y) ? (y) : (x) #define E(x) (1 << (x)) #define iabs(x) (x) < 0 ? -(x) : (x) #define OUT(x) printf("%I64d ", x) #define lowbit(x) (x)&(-x) #define Read() freopen("a.txt", "r", stdin) #define Write() freopen("b.txt", "w", stdout); #define maxn 1000000000 #define N 2510 #define mod 1000000000 using namespace std; struct point { int x,y,step,state; }; int n,m,t; int dir[4][2]={-1,0,1,0,0,1,0,-1}; char maze[25][25]; int vis[25][25][1<<10]; int ex,ey; int get(char c) { return c-(islower(c)?'a':'A'); //转化为 数字 'a'为0 } void bfs(int sx,int sy) { point s; s.x=sx,s.y=sy,s.step=0,s.state=0; memset(vis,0,sizeof(vis)); vis[s.x][s.y][0]=1; queue<point>que; que.push(s); while(!que.empty()) { point e=que.front(); que.pop(); // printf("%d %d %d %d ",e.x,e.y,e.step,e.state); if(e.x==ex&&e.y==ey) {printf("%d ",e.step);return;} for(int i=0;i<4;i++) { s.x=e.x+dir[i][0]; s.y=e.y+dir[i][1]; s.state=e.state; if(s.x>=0&&s.x<n&&s.y>=0&&s.y<m&&maze[s.x][s.y]!='*') { //判断是否有相应钥匙 if(isupper(maze[s.x][s.y])&&(!(e.state&(1<<get(maze[s.x][s.y]))))) continue; if(islower(maze[s.x][s.y])) //遇到钥匙 { //printf("%d ",1<<get(maze[s.x][s.y])); s.state|=(1<<get(maze[s.x][s.y])); } s.step=e.step+1; if(!vis[s.x][s.y][s.state]&&s.step<=t) { vis[s.x][s.y][s.state]=1; que.push(s); } } } } printf("-1 "); } int main() { //freopen("a.txt","r",stdin); int sx,sy; while(~scanf("%d%d%d",&n,&m,&t)) { t--; for(int i=0;i<n;i++) { scanf("%s",maze[i]); for(int j=0;j<m;j++) if(maze[i][j]=='@') { sx=i,sy=j; } else if(maze[i][j]=='^') { ex=i,ey=j; } } // printf("%d %d ",sx,sy); bfs(sx,sy); } return 0; }