1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5 #include <queue>  6 using namespace std;  7   8 #define MAXN 8  9  10 typedef struct { 11     int x, y; 12 } Point_t; 13  14 typedef struct { 15     Point_t v; 16     Point_t box[3]; 17     int t; 18 } Node_t; 19  20 Node_t cur; 21 bool visit[MAXN][MAXN][MAXN][MAXN][MAXN][MAXN][MAXN][MAXN]; 22 char map[MAXN+5][MAXN+5]; 23 int dir[4][2] = { 24     {-1,0}, {1,0}, {0,-1}, {0,1} 25 }; 26 int n, m; 27  28 bool check(int x, int y) { 29     return x<0 || x>=n || y<0 || y>=m || map[x][y]==‘#‘; 30 } 31  32 bool getVisit(Node_t a) { 33     return     visit[a.v.x][a.v.y][a.box[0].x][a.box[0].y][a.box[1].x][a.box[1].y][a.box[2].x][a.box[2].y]; 34 } 35  36 void setVisit(Node_t a) { 37     visit[a.v.x][a.v.y][a.box[0].x][a.box[0].y][a.box[1].x][a.box[1].y][a.box[2].x][a.box[2].y] = true; 38 } 39  40 bool isFinish(Node_t a) { 41     return map[a.box[0].x][a.box[0].y]==‘@‘ && map[a.box[1].x][a.box[1].y]==‘@‘ && 42             map[a.box[2].x][a.box[2].y]==‘@‘; 43 } 44  45 bool boxCanMove(Node_t a, int d, int id) { 46     int x = a.v.x + dir[d][0]; 47     int y = a.v.y + dir[d][1]; 48  49     if (check(x, y)) 50         return false; 51  52     for (int i=0; i<3; ++i) { 53         if (i!=id && a.box[i].x==x && a.box[i].y==y) 54             return false; 55     } 56  57     return true; 58 } 59  60 void printNode(Node_t a) { 61     printf("a.v.x = %d, a.v.y = %d\n", a.v.x, a.v.y); 62     for (int i=0; i<3; ++i) { 63         printf("a.box[%d].x = %d, a.box[%d].y = %d\n", i, a.box[0].x, i, a.box[0].y); 64     } 65 } 66  67 int bfs() { 68     queue<Node_t> Q; 69     int i, j, k; 70     int x, y; 71  72     memset(visit, false, sizeof(visit)); 73     cur.t = 0; 74     setVisit(cur); 75     Q.push(cur); 76  77     while (!Q.empty()) { 78         Node_t d = Q.front(); 79         Q.pop(); 80 #ifndef ONLINE_JUDGE 81         printNode(d); 82 #endif 83         if (isFinish(d)) { 84             return d.t; 85         } 86  87         for (i=0; i<4; ++i) { 88             x = d.v.x + dir[i][0]; 89             y = d.v.y + dir[i][1]; 90             if (check(x, y)) 91                 continue; 92             Node_t nd = d; 93             nd.v.x = x; 94             nd.v.y = y; 95             ++nd.t; 96             for (j=0; j<3; ++j) { 97                 if (nd.box[j].x == x && nd.box[j].y == y) { 98                     break; 99                 }100             }101             if (j<3) {102                 /* next is a box*/103                 if (boxCanMove(nd, i, j)) {104                     nd.box[j].x += dir[i][0];105                     nd.box[j].y += dir[i][1];106                 } else {107                     continue;108                 }109             }110 111             if (!getVisit(nd)) {112                 setVisit(nd);113                 Q.push(nd);114             }115         }116     }117 118     return -1;119 }120 121 int main() {122     int i, j, k;123 124     #ifndef ONLINE_JUDGE125         freopen("data.in", "r", stdin);126     #endif127 128     while (scanf("%d %d", &n, &m) != EOF) {129         k = 0;130         for (i=0; i<n; ++i) {131             scanf("%s", map[i]);132             for (j=0; j<m; ++j) {133                 if (map[i][j] == ‘X‘) {134                     cur.v.x = i;135                     cur.v.y = j;136                 } else if (map[i][j] == ‘*‘) {137                     cur.box[k].x = i;138                     cur.box[k].y = j;139                     ++k;140                 }141             }142         }143 144         k = bfs();145         printf("%d\n", k);146     }147 148     return 0;149 }