公主生气了，现在wh需要集齐 X 种云（帽子云，波浪云。。。）让公主开心。开始wh在一个迷宫的入口处，迷宫里恰好有 X 种云，每种云恰好只有一个。
wh每一步可以向上，向下，向左，向右走一步。请帮助wh计算最少需要走多少步收集到所有的云朵。由于wh有特殊 的技能，所以不用考虑wh该怎么走出去~
1482: find clouds
Time Limit: 3 Sec Memory Limit: 128 MB 64bit IO Format: %lldSubmitted: 69 Accepted: 14
[Submit][Status][Web Board]
Description
Input
第一行 n,m,k,迷宫有n行,m列,里面有 k 种云朵。接下来有n行，每行有m个字符。字符只包括 '.' , '#' , 's'和数字xi(1<=i<=k，0<=xi<k)。
'.'表示wh可以走到当前位置，'#'表示该位置不可达,'S'表示迷宫的入口，数字xi表 示这个位置是第i种云朵。迷宫的边缘部分全部是'#',只有一个入口。
(10<=n,m<=100,0<=k<=10)
Output
; 若可以收齐所有的云朵，输出最少的步数。否则输出 "bengkala".
Sample Input
10 10
2
##########
#.####.0.#
#..#.....#
#.#1..##.#
#.#.#....#
#......#.#
#.S#.#..##
#.#.#....#
#...######
##########Sample Output
10
题解：
这题不想吐槽了，同样的代码交了3遍，前两遍tle，第三遍ac了。。。还拿小号做了n次实验。。不得不说这是一道人品题（或许是我太弱了，想不出更好的方法）。。给的测试数据小就过得快，而且这题还搜不到题解对不对（手动滑稽）,毕竟这是我们学校acm原创题，为了造福后人，写一个题解吧，这题算是搜索入门和进阶之间的题目吧，要有一定基础才能做出来，重点就是状态的保存，因为只有有钥匙和没钥匙（云就叫钥匙吧，大多数题都是以钥匙出现）两种状态，我们用二进制保存，每一位1和0就是当前钥匙有和无，假如要有k把钥匙，那么需要的内存为1<<k，每一次bfs，获得当前节点状态key，那么怎么获得钥匙情况呢，就拿当前地图的钥匙情况与key做&运算（有点难理解，理解一下），假如当前钥匙没有取，就把key的状态做|运算（理解啊理解）,只要会了状态压缩，那么这题就简单了
ps：
手动赋值p数组超时了n次，改成memset就过了。。好迷啊
下面是代码：
#include<stdio.h>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
using namespace std;
struct node
{int x,y;int step;//保存步数int key;//保存钥匙情况int num;//保存当前钥匙数目
};
int p[101][101][1025];//三维数组储存状态
int dirx[4]={0,0,-1,1};
int diry[4]={-1,1,0,0};//方向数组
char s[105][105];//存图
int n,m,k,stx,sty;
queue<node>q;
int main()
{int i,j,r,w,xx,yy,tag;node now,next;while(scanf("%d%d",&n,&m)!=EOF){memset(p,0,sizeof(p));scanf("%d",&k);tag=0;for(i=0;i<n;i++){scanf("%s",s[i]);if(!tag)for(j=0;j<m;j++){if(s[i][j]=='S')//保存初始位置{stx=i;sty=j;tag=1;}}}if(k==0){printf("0\n");continue;}while(!q.empty())q.pop();now.x=stx;now.y=sty;now.step=0;now.key=0;now.num=0;p[stx][sty][0]=1;q.push(now);w=-1;//纪录如果可达的步数while(!q.empty())//bfs{now=q.front();q.pop();for(i=0;i<4;i++){xx=now.x+dirx[i];yy=now.y+diry[i];int key=now.key;next.num=now.num;if(xx<0||yy<0||xx>=n||yy>=m||s[xx][yy]=='#')continue;if(s[xx][yy]>='0'&&s[xx][yy]<='9')//获得钥匙状态，是否取了当前的钥匙{int add=s[xx][yy]-'0';if(key&(1<<add))//重点理解！！！continue;elsekey=key|(1<<add);//重点理解！！！next.num++;}if(!p[xx][yy][key])//当前状态没被覆盖{next.x=xx;next.y=yy;next.key=key;next.step=now.step+1;if(next.num>=k)//找到了立即退出{w=next.step;goto loop;}q.push(next);p[xx][yy][key]=1;}}}loop:;if(w==-1){printf("bengkala\n");}elseprintf("%d\n",w);}return 0;
}