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());

    }

}