HDU Stealing Harry Potter's Precious(状压BFS)

状压BFS

注意在用二维字符数组时,要把空格、换行处理好。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
int sx,sy,C,n,m;
int ans;
bool vis[][][<<];
char g[][];
int key[][];
int dx[]={,,-,},dy[]={,,,-};
bool check(int a,int b){return <=a&&a<=n&&<=b&&b<=m;}
bool ok(int mask)
{
for(int i=;i<=C;i++)
if(mask&(<<i));
else return false;
return true;
}
struct mask
{
int x,y,key,step;
mask(int x,int y,int key,int step):x(x),y(y),key(key),step(step){};
};
queue<mask>q;
int bfs()
{//printf("%d %d",sx,sy);
while(q.size())q.pop();
memset(vis,false,sizeof(vis));
q.push(mask(sx,sy,,));
vis[sx][sy][]=true;
while(q.size())
{
mask tmp=q.front();q.pop();//printf("%d %d %d\n",tmp.x,tmp.y,tmp.key);
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;//printf("%d %d\n",nx,ny);
if(check(nx,ny)&&!vis[nx][ny][nkey]&&g[nx][ny]!='#')
{
if(key[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)){
getchar();//这里的getchar()吸收掉换行,刚刚没注意这里WA后,想了半个钟,可恨啊。。。。
if(n==&&m==)break;
ans=INF;
memset(key,,sizeof(key));
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
scanf("%c",&g[i][j]);
if(g[i][j]=='@')
{
sx=i;
sy=j;
}
}
getchar();
}
/* for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%c",g[i][j]);
printf("\n");
}*/
scanf("%d",&C);
int a,b;
for(int i=;i<=C;i++)
{
scanf("%d %d",&a,&b);
key[a][b]=<<i;
}
printf("%d\n",bfs());
}
}
上一篇:状压BFS


下一篇:为镜像添加SSH服务