1 #include <cstdio>  2 #include <cstring>  3 #include <queue>  4 #include <algorithm>  5 using namespace std;  6   7 char g[10][10];  8 int n,m;  9 int sx,sy; 10 bool vis[9][9][9][9][9][9][9][9]; 11 int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; 12 struct node 13 { 14     int x[4],y[4],xx,yy,step; 15 } st1,st2,st; 16  17 int deal(node p,int i,int pos) 18 { 19     p.xx+=dir[i][0]; 20     p.yy+=dir[i][1]; 21     if(p.xx>=0&&p.xx<n&&p.yy>=0&&p.yy<m) 22     { 23         for(int j=0; j<3; j++) 24         { 25             if(j!=pos&&p.x[j]==p.xx&&p.y[j]==p.yy) 26             { 27                 return 0; 28             } 29         } 30         return 1; 31     } 32     return 0; 33 } 34  35 int bfs() 36 { 37     queue<node>q; 38     st.step=0; 39     st.xx=sx; 40     st.yy=sy; 41     q.push(st); 42     memset(vis,false,sizeof(vis)); 43     vis[sx][sy][st.x[0]][st.y[0]][st.x[1]][st.y[1]][st.x[2]][st.y[2]]=true; 44     while(!q.empty()) 45     { 46         st1=q.front(); 47         q.pop(); 48         int cnt=0; 49         for(int i=0; i<3; i++) 50         { 51             if(g[st1.x[i]][st1.y[i]]==‘@‘) 52             { 53                 cnt++; 54             } 55         } 56         if(cnt==3) 57         { 58             return st1.step; 59         } 60         for(int i=0; i<4; i++) 61         { 62             st2=st1; 63             st2.xx=st2.xx+dir[i][0]; 64             st2.yy=st2.yy+dir[i][1]; 65             st2.step++; 66             if(st2.xx>=0&&st2.xx<n&&st2.yy>=0&&st2.yy<m&&g[st2.xx][st2.yy]!=‘#‘) 67             { 68                 int pos; 69                 for(pos=0; pos<3; pos++) 70                 { 71                     if(st2.x[pos]==st2.xx&&st2.y[pos]==st2.yy) 72                     { 73                         break; 74                     } 75                 } 76                 if(pos<3) 77                 { 78                     if(deal(st2,i,pos)) 79                     { 80                         st2.x[pos]+=dir[i][0]; 81                         st2.y[pos]+=dir[i][1]; 82                         if(!vis[st2.xx][st2.yy][st2.x[0]][st2.y[0]][st2.x[1]][st2.y[1]][st2.x[2]][st2.y[2]]) 83                         { 84                             vis[st2.xx][st2.yy][st2.x[0]][st2.y[0]][st2.x[1]][st2.y[1]][st2.x[2]][st2.y[2]]=true; 85                             q.push(st2); 86                         } 87                     } 88                 } 89                 else 90                 { 91                     if(!vis[st2.xx][st2.yy][st2.x[0]][st2.y[0]][st2.x[1]][st2.y[1]][st2.x[2]][st2.y[2]]) 92                     { 93                         vis[st2.xx][st2.yy][st2.x[0]][st2.y[0]][st2.x[1]][st2.y[1]][st2.x[2]][st2.y[2]]=true; 94                         q.push(st2); 95                     } 96                 } 97             } 98         } 99     }100     return -1;101 }102 103 int main()104 {105     while(scanf("%d%d",&n,&m)!=EOF)106     {107         int num=0;108         for(int i=0; i<n; i++)109         {110             scanf("%s",g[i]);111             for(int j=0; j<m; j++)112             {113                 if(g[i][j]==‘X‘)114                 {115                     g[i][j]=‘.‘;116                     sx=i;117                     sy=j;118                 }119                 else if(g[i][j]==‘*‘)120                 {121                     g[i][j]=‘.‘;122                     st.x[num]=i;123                     st.y[num]=j;124                     num++;125                 }126             }127         }128         printf("%d\n",bfs());129     }130     return 0;131 }