题意：1个机器人找几个垃圾，求出最短路径。
状压BFS，这道题不能用普通BFS二维vis标记数组去标记走过的路径，因为这题是可以往回走的，而且你也不能只记录垃圾的数量就可以了，因为它有可能重复走同一个垃圾。其实解决的办法就是把vis标记数组开到3维，用来存每次走的状态。再通过位运算即可。
下面是2中常见的位运算操作：
1、加入某一个垃圾：rubblish | =（ 1 << i );
eg: 0001 | 0100 =0101 ;
2、进行垃圾匹配 ：if（ （ rubblish & （ 1 << i ) ） = = 0 ) continue;（注意括号的位置）
eg: 0010 &1001=0 不匹配；
0010 & 1011=1；可以匹配。
谨记：以后像这种找垃圾、找钥匙去开门、可以跨越障碍求最短路径等等的题目，就可以考虑用状压BFS。(一般这些垃圾。钥匙不会超过10个，因为那样三维数组存不下）
还有这题也可以用TSP去解。
#include<stdio.h>
#include<string.h>
#define INF 0x3f3f3f3f
#include<algorithm>
#include<queue>
using namespace std;
bool vis[][][<<];//vis数组存的是垃圾的状态
char g[][];
int key[][];//垃圾种类
int ans=INF;
int n,m,sx,sy;
int dx[]={,,-,},dy[]={,,,-};
int C;
struct mask
{
int x,y,key,step;
mask(int x,int y,int key,int step):x(x),y(y),key(key),step(step){};
};
bool check(int a,int b){return <=a&&a<m&&<=b&&b<n;}
//判断是否找到所有的垃圾
bool OK(int mask)
{
for(int i=;i<C;i++)
{
if(mask&<<i);
else return false;
}
return true;
}
int bfs()
{
queue<mask>q;
while(q.size())q.pop();
q.push(mask(sx,sy,,));
memset(vis,false,sizeof(vis));
vis[sx][sy][]=true;
while(q.size()){
mask tmp=q.front();q.pop();
if(OK(tmp.key))
{
ans=min(ans,tmp.step);
}
for(int i=;i<;i++)
{
int nx=tmp.x+dx[i];
int ny=tmp.y+dy[i];
int nkey=tmp.key;
if(g[nx][ny]!='x'&&check(nx,ny)&&!vis[nx][ny][nkey])
{
if(g[nx][ny]=='*')
{
nkey|=key[nx][ny];
}
vis[nx][ny][nkey]=true;
q.push(mask(nx,ny,nkey,tmp.step+));
}
}
}
return ans==INF?-:ans;
}
int main()
{
while(~scanf("%d %d",&n,&m)){
if(n==&&m==)break;
C=;
ans=INF;
memset(key,,sizeof(key));
for(int i=;i<m;i++)
{
scanf("%s",g[i]);
for(int j=;j<n;j++)
{
if(g[i][j]=='o')
{
sx=i;
sy=j;
}
if(g[i][j]=='*')
{
key[i][j]=<<C++;//预处理，把要清理的垃圾存入key数组中，即把第C个垃圾加入到key中
}
}
}
printf("%d\n",bfs());
}
}