hdu 1429

http://acm.hdu.edu.cn/showproblem.php?pid=1429
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<queue>
  5 using namespace std;
  6 char g[100][100];
  7 int vis[30][30][1026];
  8 int a[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
  9 int n,m,sx,sy,ex,ey,step;
 10 
 11 struct node
 12 {
 13     int x,y,k,step;
 14 }st,st1;
 15 
 16 void bfs()
 17 {
 18    memset(vis,0,sizeof(vis));
 19    queue<node>q;
 20    st.x=sx;
 21    st.y=sy;
 22    st.k=0;
 23    st.step=0;
 24    q.push(st);
 25    vis[sx][sy][st.k]=true;
 26    while(!q.empty())
 27    {
 28        int xx,yy;
 29        st1=q.front();
 30        q.pop();
 31        if(st1.x==ex&&st1.y==ey){step=st1.step;return;}
 32        for(int i=0; i<4; i++)
 33        {
 34            xx=st1.x+a[i][0];
 35            yy=st1.y+a[i][1];
 36            if((xx>=0&&xx<n&&yy>=0&&yy<m)&&(!vis[xx][yy][st1.k])&&g[xx][yy]!='*')
 37            {
 38                if(g[xx][yy]=='.'||g[xx][yy]=='@'||g[xx][yy]=='^')
 39                {
 40                    vis[xx][yy][st1.k]=true;
 41                    st.step=st1.step+1;
 42                    st.x=xx;
 43                    st.y=yy;
 44                    st.k=st1.k;
 45                    q.push(st);
 46                }
 47                else if(g[xx][yy]>='A'&&g[xx][yy]<='J')
 48                {
 49                    if((1<<(g[xx][yy]-'A'))&st1.k)
 50                    {
 51                        vis[xx][yy][st1.k]=true;
 52                        st.step=st1.step+1;
 53                        st.x=xx;
 54                        st.y=yy;
 55                        st.k=st1.k;
 56                        q.push(st);
 57                    }
 58                }
 59                else if(g[xx][yy]>='a'&&g[xx][yy]<='j')
 60                {
 61                    int key=((1<<(g[xx][yy]-'a'))|st1.k);
 62                    if(!vis[xx][yy][key])
 63                    {
 64                        vis[xx][yy][key]=true;
 65                        st.k=key;
 66                        st.x=xx;
 67                        st.y=yy;
 68                        st.step=st1.step+1;
 69                        q.push(st);
 70                    }
 71                }
 72            }
 73        }
 74    }
 75 }
 76 
 77 int main()
 78 {
 79     int t;
 80     while(scanf("%d%d%d",&n,&m,&t)==3){
 81         step=-1;
 82         for(int i=0; i<n; i++)
 83         {
 84             scanf("%s",g[i]);
 85             for(int j=0; j<m; j++)
 86             {
 87                 if(g[i][j]=='@')
 88                 {
 89                     sx=i;
 90                     sy=j;
 91                 }
 92                 else if(g[i][j]=='^')
 93                 {
 94                     ex=i;
 95                     ey=j;
 96                 }
 97             }
 98         }
 99         bfs();
100         if(step>=t||step==-1) printf("-1
");
101         else
102         printf("%d
",step);
103     }
104     return 0;
105 }
View Code