学步园

去年写这一题不知道BFS要避免重复访问相同的状态，一直MLE。。拖了一年开始写了。

很明显的状态压缩，used[x][y][key]用来标记表示在[x,y]点处拿到key的宝物的状态，key用二进制数表示是否取得了某一个宝物，例如1001表示取得了第一个和第四个宝物。

然后这次因为访问的状态表急错了也MLE了几次。。==

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;

int N;
int M;
int K;
int mp[110][110];
int used[110][110][1<<4];
//int d[110][110][1<<4];
int ans;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
struct node
{
public:
    int x;
    int y;
    int key;
    int step;
    node(){}
    node(int xx,int yy,int k,int s)
    {
        x=xx;
        y=yy;
        key=k;
        step=s;
    }
};
pair<int,int> st;
pair<int,int> prec[4];
queue<node>q;
void bfs()
{
    while(!q.empty()) q.pop();
    int s=0;
    if(mp[st.first][st.second]>=2)
    {
        s=(1<<mp[st.first][st.second])-2;
    }
    node a=node(st.first,st.second,s,0);
    q.push(a);
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop();
        int x=tmp.x;
        int y=tmp.y;
        int key=tmp.key;
        int step=tmp.step;
        used[x][y][key]=false;
   //    cout<<x<<" "<<y<<" "<<key<<" "<<step<<endl;

        if(key==((1<<K)-1))
        {
            ans=step;//need to get min?
            return;
        }
        for(int i=0;i<4;i++)
        {
            if(x+dx[i]>=1&&x+dx[i]<=N&&y+dy[i]>=1&&y+dy[i]<=M&&mp[x+dx[i]][y+dy[i]]>=1)//used[x+dx[i]][y+dy[i]]&& 该点是否走过要根据下面key的状态判断，我都不造这里USED只写了两维怎么还能进if的
            {
                if(mp[x+dx[i]][y+dy[i]]>=2&&mp[x+dx[i]][y+dy[i]]<=(K+1))
                {
                    int new_k=mp[x+dx[i]][y+dy[i]]-2;//这里米有考虑两个宝物在同一个格子里的case
                   // if((key&(1<<new_k))==0)//used在下面才判定，所以这里不能有if
                //    {
                        if(used[x+dx[i]][y+dy[i]][key|(1<<new_k)]==false) continue;
                        node tmp2=node(x+dx[i],y+dy[i],key|(1<<new_k),step+1);
                        q.push(tmp2);
                        used[x+dx[i]][y+dy[i]][key|(1<<new_k)]=false;//一定要标记访问，否则会MLE
                 //   }

                }
                else
                {
                    if(used[x+dx[i]][y+dy[i]][key]==false) continue;
                    node tmp2=node(x+dx[i],y+dy[i],key,step+1);
                    q.push(tmp2);
                    used[x+dx[i]][y+dy[i]][key]=false;
                }
            }
        }

    }


}
int main()
{
    freopen("input.txt","r",stdin);
    // freopen("data.txt","r",stdin);
     //freopen("out1.txt","w",stdout);
     while(true)
     {
         scanf("%d %d",&N,&M);
         memset(used,true,sizeof(used));
         memset(mp,true,sizeof(mp));
         ans=-1;
         if(N==0&&M==0) break;
         else
         {
             for(int i=1;i<=N;i++)
             {
                 for(int j=1;j<=M;j++)
                 {
                     char str;
                     cin>>str;
                     if(str=='#') mp[i][j]=0;
                     else if(str=='.') mp[i][j]=1;
                     else if(str=='@')
                     {
                         mp[i][j]=0;
                         st.first=i;
                         st.second=j;
                     }
                 }
             }
         }
         scanf("%d",&K);
         for(int i=0;i<K;i++)
         {
             int x,y=0;
             scanf("%d %d",&x,&y);
             mp[x][y]=i+2;
             prec[i]=make_pair(x,y);
         }
         bfs();
         printf("%d\n",ans);
        // puts(" ");
     }
    return 0;
}