推箱子

import sys
import collections

def moveBox(bmap, N, M):
    dic = ((1,0), (-1,0), (0,1), (0,-1))
    for i in range(N):
        for j in range(M):
            if bmap[i][j] == '*':
                box = [i, j]
            if bmap[i][j] == 'X':
                people = [i, j]
    dp = [[[[False for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]
    dp[box[0]][box[1]][people[0]][people[1]] = True
    stack = collections.deque([[box[0], box[1], people[0], people[1]]])
    step = 0
    while stack:
        step += 1
        lenth = len(stack)
        for _ in range(lenth):
            bx, by, px, py = stack.popleft()
            for dx, dy in dic:
                nx, ny = px + dx, py + dy
                # can move
                if -1 < nx < N and -1 < ny < M and bmap[nx][ny] != '#':
                    # touch the box, move the box
                    if nx == bx and ny == by:
                        nbx, nby = bx+dx, by+dy
                        # the box is in range
                        if -1 < nbx < N and -1 < nby < M:
                            # arrive the target
                            if bmap[nbx][nby] == '@':
                                return step
                            else:
                                # first arrive, keep the state
                                if not dp[nbx][nby][nx][ny]:
                                    dp[bx+dx][by+dy][nx][ny] = True
                                    stack.append([bx+dx, by+dy, nx, ny])
                    else:
                        # keep the state
                        if not dp[bx][by][nx][ny]:
                            dp[bx][by][nx][ny] = True
                            stack.append([bx, by, nx, ny])
    return -1
                
                    

                    
if __name__ == '__main__':
    sin = sys.stdin
    #sin = open('move_box.txt')
    while True:
        line = sin.readline()
        if not line:
            break
##        line = line.splitlines()[0]
        N, M = [int(t) for t in line.split()]
        bmap = []
        for _ in range(N):
            bmap.append([ch for ch in sin.readline().splitlines()[0]])
        print(moveBox(bmap, N, M)) 

开个四维vis[x][y][xb][yb]代表人在(x,y)，箱子在(xb,yb)这个状态的最小步数。
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
struct q{

	    int x,y,xb,yb;



	    q(int x,int y,int xb,int yb):x(x),y(y),xb(xb),yb(yb){}



	};



	int a[]={0,0,1,-1},b[]={1,-1,0,0};



	char mp[10][10];



	int vis[10][10][10][10];



	int bx,by,sx,sy,ex,ey,n,m;



	int bfs()



	{



	    vis[sx][sy][bx][by]=1;



	   q p(sx,sy,bx,by);



	    queue<q> que;



	    que.push(p);



	    while(que.size())



	    {



	        p=que.front();que.pop();



	        if(p.xb==ex&&p.yb==ey)return vis[p.x][p.y][p.xb][p.yb]-1;



	        for(int i=0;i<4;i++)



	        {



	            int nx=p.x+a[i],ny=p.y+b[i];



	            if(nx<0||ny<0||mp[nx][ny]=='#'||nx>=n||ny>=m)continue;



	            if(nx==p.xb&&ny==p.yb)



	            {



	                if(nx+a[i]<0||ny+b[i]<0||mp[nx+a[i]][ny+b[i]]=='#'||nx+a[i]>=n||ny+b[i]>=m)continue;



	                if(vis[nx][ny][nx+a[i]][ny+b[i]])continue;



	               vis[nx][ny][nx+a[i]][ny+b[i]]=vis[p.x][p.y][p.xb][p.yb]+1;



	               que.push(q(nx,ny,nx+a[i],ny+b[i]));



	            }



	            else{



	                if(vis[nx][ny][p.xb][p.yb])continue;



	                vis[nx][ny][p.xb][p.yb]=vis[p.x][p.y][p.xb][p.yb]+1;



	                que.push(q(nx,ny,p.xb,p.yb));



	            }



	        }



	    }



	    return -1;



	}



	int main()



	{



	    scanf("%d%d",&n,&m);



	    for(int i=0;i<n;i++)



	        scanf("%s",mp[i]);



	    for(int i=0;i<n;i++)



	        for(int j=0;j<m;j++)



	        if(mp[i][j]=='*')bx=i,by=j;



	        else if(mp[i][j]=='X')sx=i,sy=j;



	        else if(mp[i][j]=='@')ex=i,ey=j;



	   cout<<bfs()<<endl;



	   return 0;



	}

做法是，只有人是主动的有四个方向。
情况1：如果人走到了一个点，而且这个点恰好是箱子，那么箱子自然也要与人同样的方向移动。 此时需要判断人和箱子的位置是否都满足 既不是障碍，也不出图
情况2：只有人走了一个点，这个点不是箱子，那么自然不需要判断箱子的情况了。
开个四维数组， 两维给人记录X,Y， 另外两维给箱子记录X,Y。
这样就是裸的bfs

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

typedef long long ll;

char mp[10][10];
int vis[10][10][10][10];
int data[4][2]={0,1,0,-1,1,0,-1,0};
    int n,m;
struct node{
    int x,y,step;
    int xx,yy;
    node(int _x,int _y,int _step,int _xx,int _yy){x=_x,y=_y,step=_step,xx=_xx,yy=_yy;}
};
int bfs(int sxx,int syy,int sx,int sy){
    queue<node> q;
    q.push(node(sx,sy,0,sxx,syy));
    while(!q.empty())
    {
        node s=q.front();
        q.pop();
        vis[s.x][s.y][s.xx][s.yy]=1;
        //cout<<s.x <<" "<<s.y<<" "<<s.xx<<" "<<s.yy<<" "<<s.step<<endl;
        if(mp[s.xx][s.yy]=='@') return s.step;
        for(int i=0;i<4;i++){
            node tmp=s;
            tmp.step++;
            tmp.x+=data[i][0];
            tmp.y+=data[i][1];

            if(tmp.x>n||tmp.y>m||tmp.x<1||tmp.y<1) continue;

            if(mp[tmp.x][tmp.y]=='#') continue;

            if(tmp.x==tmp.xx&&tmp.y==tmp.yy)
                tmp.xx+=data[i][0],tmp.yy+=data[i][1];

            if(tmp.xx>n||tmp.yy>m||tmp.xx<1||tmp.yy<1) continue;

            if(mp[tmp.xx][tmp.yy]=='#') continue;

            if(vis[tmp.x][tmp.y][tmp.xx][tmp.yy]!=1)
                q.push(tmp);
        }
    }
    return -1;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>&mp[i][1];
    int sx,sy,xx,yy;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(mp[i][j]=='X')
            sx=i,sy=j;
            if(mp[i][j]=='*')
            xx=i,yy=j;
        }
    }
    cout<<bfs(xx,yy,sx,sy)<<endl;
}
/*
3 3
#.X
#*.
@..
*/

参考@周昆的代码，加了一些注释便于大家理解

# 前两位表示箱子的起始位置，后两位表示玩家的位置
start = [-1] * 4 
end = [-1] * 2
n, m = map(int, input().split())
mat = list()
for i in range(n):
    line = input()
    mat.append(line)
    for j in range(len(line)):
        # box pos
        if line[j] == '*':
            start[0], start[1] = i, j
        # player pos
        if line[j] == 'X':
            start[2], start[3] = i, j
        # dest pos
        if line[j] == '@':
            end[0], end[1] = i, j
# 四维表用以记录箱子的x,y及玩家的x,y
reach = [[[[-1 for _ in range(m)] for _ in range(n)] for _ in range(m)] for _ in range(n)]
queue = list()
queue.append(start)
direction = ((0, 1), (1, 0), (0, -1), (-1, 0))
reach[start[0]][start[1]][start[2]][start[3]] = 0
while len(queue):
    cur = queue.pop(0)
    if cur[0] == end[0] and cur[1] == end[1]:
        print(reach[cur[0]][cur[1]][cur[2]][cur[3]])
        break
    # 可以往四个方向推
    for i in range(4):
        player_x = cur[2] + direction[i][0]
        player_y = cur[3] + direction[i][1]
        # 检查箱子和玩家位置是否合法
        if 0 <= player_x < n and 0 <= player_y < m and mat[player_x][player_y] != '#':
            # 检查玩家和箱子是否重合
            if player_x == cur[0] and player_y == cur[1]:
                # 重合的时候将箱子往同一个方向推并检查箱子状态是否合法
                box_x, box_y = cur[0] + direction[i][0], cur[1] + direction[i][1]
                if box_x < 0 or box_x >= n or box_y < 0 or box_y >= m or mat[box_x][box_y] == '#':
                    continue
            else:
                # 如果不重合则箱子位置不动
                box_x, box_y = cur[0], cur[1]
            # 判断该点是否已经遍历过
            if reach[box_x][box_y][player_x][player_y] < 0:
                queue.append([box_x, box_y, player_x, player_y])
                reach[box_x][box_y][player_x][player_y] = reach[cur[0]][cur[1]][cur[2]][cur[3]] + 1
if cur[0] != end[0] or cur[1] != end[1]:
    print(-1)

from collections import deque
start = [0] * 4
end = [0] * 2
N, M = map(int, raw_input().split())
maze = []
for i in range(N):
	maze.append([])
	for j, s in enumerate(raw_input()):
		maze[i].append(s)
		if s == '*':
			start[0], start[1] = i, j
		elif s == 'X':
			start[2], start[3] = i, j
		elif s =='@':
			end[0], end[1] = i, j
# box_x, box_y, per_x, per_y
reach = [[[[-1 for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]
mazeQueue = deque()
mazeQueue.append(start)
direction = ((0, 1), (1, 0), (0, -1), (-1, 0))
reach[start[0]][start[1]][start[2]][start[3]] = 0
while len(mazeQueue):
	point = mazeQueue.popleft()
	if point[0]  == end[0] and point[1] == end[1]:
		print reach[point[0]][point[1]][point[2]][point[3]]
		break
	for i in range(4):
		# new coordinate for person
		xper = point[2]+direction[i][0]
		yper = point[3]+direction[i][1]
		# check validity 
		if 0 <= xper < N and 0 <= yper < M and maze[xper][yper] != "#":
			if xper == point[0] and yper == point[1]:
				xbox, ybox = point[0] + direction[i][0], point[1] + direction[i][1]
				if xbox < 0 or xbox >= N or ybox < 0 or ybox >= M or maze[xbox][ybox] == '#':
					continue
			else:
				xbox, ybox = point[0], point[1]
			if reach[xbox][ybox][xper][yper] < 0:
				mazeQueue.append([xbox, ybox, xper, yper])
				reach[xbox][ybox][xper][yper] = reach[point[0]][point[1]][point[2]][point[3]] + 1
if point[0]  != end[0] or point[1] != end[1]:
	print -1

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Created by Administrator on 2017/3/16.
 */

class Stage{
    public Stage(int peoplex, int peopley) {
        this.peoplex = peoplex;
        this.peopley = peopley;
    }

    public Stage(int peoplex, int peopley, int boxx, int boxy) {
        this.peoplex = peoplex;
        this.peopley = peopley;
        this.boxx = boxx;
        this.boxy = boxy;
    }

    @Override
    public String toString() {
        return "people:("+this.peoplex+","+this.peopley+")  box:("+this.boxx+","+this.boxy+")";
    }

    public Stage() {
    }

    int peoplex;
    int peopley;
    int boxx;
    int boxy;
    Stage previous;

    public boolean equals(Object obj) {
        if (obj instanceof Stage) {
            if (((Stage) obj).peoplex==peoplex&&((Stage) obj).peopley==peopley&&((Stage) obj).boxx==boxx&&((Stage) obj).boxy==boxy)return true;
        }
        return false;
    }
}

public class test12 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            char[][] map = new char[n][m];
            for (int i=0;i<n;i++){
                map[i] = sc.next().toCharArray();
            }
            int peoplex=0;
            int peopley=0;
            int boxx=0;
            int boxy=0;
            for (int i=0;i<n;i++){
                for (int j=0;j<m;j++){
                    if (map[i][j]=='X'){
                        peoplex=i;
                        peopley=j;
                    }
                    if (map[i][j]=='*'){
                        boxx=i;
                        boxy=j;
                    }
                }
            }

            Stage begin = new Stage(peoplex,peopley,boxx,boxy);
            System.out.println(begin);
            Stage result = BFS(begin,map,m,n);
            if (result==null){
                System.out.println(-1);
            }else {
                while (result.previous!=null){
                    System.out.println(result.previous);
                    result = result.previous;
                }
            }
        }
    }

    public static Stage BFS(Stage begin,char[][] map,int m,int n){
        Queue<Stage> queue = new LinkedList<Stage>();
        ArrayList<Stage> arrayList = new ArrayList<Stage>();
        int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};

        queue.offer(begin);
        while(!queue.isEmpty()){
            Stage local = queue.remove();
            arrayList.add(local);
            for(int i=0; i< dir.length; i++){
                Stage next = new Stage(local.peoplex+dir[i][0], local.peopley+dir[i][1]);
                next.previous = local;
                if (next.peoplex>=0&&next.peoplex<m&&next.peopley<n&&next.peopley>=0&&map[next.peoplex][next.peopley]!='#'){
                    if (next.peoplex==local.boxx&&next.peopley==local.boxy){
                        next.boxx=local.boxx+dir[i][0];
                        next.boxy=local.boxy+dir[i][1];
                    }else {
                        next.boxx=local.boxx;
                        next.boxy=local.boxy;
                    }
                    if (arrayList.contains(next))continue;
                    if (next.boxx>=0&&next.boxx<m&&next.boxy<n&&next.boxy>=0&&map[next.boxx][next.boxy]!='#'){
                        arrayList.add(next);
                        queue.offer(next);
                    }else {
                        continue;
                    }
                    if (map[next.boxx][next.boxy]=='@'){
                        return next;
                    }
                }
            }
        }
        return null;
    }
}

import java.util.*;
public class Main {
    private static class State {
        int px, py, bx, by;
        State pre;

        public State(int px, int py, int bx, int by, State pre) {
            this.px = px;
            this.py = py;
            this.bx = bx;
            this.by = by;
            this.pre = pre;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            int n = Integer.parseInt(s.split(" ")[0]);
            int px = -1, py = -1, bx = -1, by = -1;
            char[][] maze = new char[n][];
            for (int i = 0; i < n; i++) {
                maze[i] = sc.nextLine().toCharArray();
                for (int j = 0; j < maze[i].length; j++) {
                    if (maze[i][j] == 'X') {
                        px = i;
                        py = j;
                    } else if (maze[i][j] == '*') {
                        bx = i;
                        by = j;
                    }
                }
            }
            State start = new State(px, py, bx, by, null);
            List<State> list = bfs(maze, start);
            System.out.println(list.size() - 1);
        }

    }

    private static List<State> bfs(char[][] maze, State start) {
        int n = maze.length;
        int m = maze[0].length;
        boolean[][][][] added = new boolean[n][m][n][m];
        Queue<State> queue = new LinkedList<>();
        LinkedList<State> list = new LinkedList<>();
        queue.add(start);
        added[start.px][start.py][start.bx][start.py] = true;
        int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        State end = null;
        while (!queue.isEmpty()) {
            State cur = queue.poll();
            if (maze[cur.bx][cur.by] == '@') {
                end = cur;
                break;
            }
            for (int[] a : move) {
                State next = new State(cur.px + a[0], cur.py + a[1], cur.bx, cur.by, cur);
                if (next.px == next.bx && next.py == next.by) {
                    next.bx += a[0];
                    next.by += a[1];
                    if (next.bx < 0 || next.bx >= n || next.by < 0 || next.by >= m || maze[next.bx][next.by] == '#')
                        continue;
                } else if (next.px < 0 || next.px >= n || next.py < 0 || next.py >= m || maze[next.px][next.py] == '#') {
                    continue;
                }
                if (!added[next.px][next.py][next.bx][next.by]) {
                    queue.add(next);
                    added[next.px][next.py][next.bx][next.by] = true;
                }
            }
        }
        if (end != null) {
            while (end != null) {
                list.addFirst(end);
                end = end.pre;
            }
        }
        return list;
    }
}

人动，

以人作bfs起点

人在不越界不撞墙的情况下，有两种状态

撞箱子，不撞箱子，

撞箱子，

箱子在不越界不撞墙的情况下，

会以人的方向前进。

字符串输入到二维字符数组可以一行一行的输入

char map[10][10];

for ( int i = 1; i n; ++ i )

cin >> &map[i][1];

可以用四维数组存放人和箱子共同的状态以表示是否之前人和箱子到过此状态

int vis[10][10][10][10];

四个方向

纵轴的x加一或减一，左右平移为加0.所以为

int x[] = {0,0,1,-1};

横轴的y与x同理，但对应位置上不能同时存在1和-1，因为是上下左右，直上直下。，所以为

int y[] = {1,-1,0,0};

入队 则将其vis置为访问过，防止重复入队。

相较 出队列再检查是否到终点，入队列即检查应该比较快

因为队列可能很长，如果入队检查已经找到了，则不需要将之前的出队，节约了时间

出队检查相较入队检查只多检查了一个队头的节点。

#include <iostream>
#include <queue>
using namespace std;


char map[10][10];
int vis[10][10][10][10];
int x[] = {0,0,1,-1};
int y[] = {1,-1,0,0};
int n, m;
struct Point{
    int _px, _py;
    int _bx, _by;
    int _step;
    Point(int px, int py, int step, int bx, int by ):_px(px),_py(py),_bx(bx),_by(by),_step(step)
    {}

};

int bfs(int px, int py, int bx, int by)
{
    if ( map[bx][by] == '@ ' )
        return 0;
    queue <Point> Q;
    Q.push(Point(px,py,0,bx,by));
    vis[px][py][bx][by] = 1;
    while ( !Q.empty() )
    {
        Point point = Q.front(); Q.pop();
        for ( int i = 0; i < 4; i ++ )
        {
            Point next = point;
            ++next._step;

            next._px += x[i];
            next._py += y[i];
//人是否越界
            if ( next._px < 1 || next._px > n || next._py < 1 || next._py > m ) continue;
//人是否撞墙
            if ( map[next._px][next._py] == '#' )   continue;
//人是否撞到箱子
            if ( next._px == next._bx && next._py == next._by )
                next._bx += x[i], next._by += y[i];
//箱子是否到终点

            if ( map[next._bx][next._by] == '@ ' )           //检查是否到终点
                return point._step;
//箱子是否越界
            if ( next._bx < 1 || next._bx > n || next._by < 1 || next._by > m ) continue;
//箱子是否撞墙
            if ( map[next._bx][next._by] == '#' )   continue;
//是否访问过
            if ( vis[next._px][next._py][next._bx][next._by] != 1 )
            {//置标记
                vis[next._px][next._py][next._bx][next._by] = 1;
                Q.push(next);
            }
        }
    }


    return -1;
}







int main()
{
    cin >> n >> m;
    for ( int i = 1; i <= n; ++ i )
        cin >> &map[i][1];

    int px, py, bx, by;

    for ( int i = 1; i <= n; ++ i )
        for ( int j = 1; j <= n; ++ j )
        {
            if ( map[i][j] == 'X' )
            {
                px = i;
                py = j;
            }
            else if ( map[i][j] == '*' )
            {
                bx = i;
                by = j;
            }
        }
    cout << bfs(px,py,bx,by);


    return 0;
}

import java.util.*;
public class Main{
    public static void main(String...args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        char[][] map = new char[N+2][M+2];
        boolean[][]used = new boolean[N+2][M+2];
        for(int i=0;i<map.length;i++){
            Arrays.fill(map[i], '#');
        }

        int[] start = null;
        int[] end = null;
        int[] box = null;
        for(int i=1;i<map.length-1;i++){
            int j=1;
            for(char ch: scan.next().toCharArray()) {
                map[i][j] = ch;
                if (ch == 'X') {
                    start = new int[]{i, j};
                }
                if (ch == '@') {
                    end = new int[]{i, j};
                }
                if (ch == '*') {
                    box = new int[]{i, j};
                }
                j++;
            }
        }
        int res = findWay(map, used, start, end, box, 0);
        System.out.println(res);
    }
    private static int findWay(char[][]map, boolean[][]used, int[] start, int[] end, int[] box, int wayLen){
        if(box[0] == end[0] && box[1] == end[1]){
            return wayLen;
        }
        else{
            int res = Integer.MAX_VALUE;
            int[]curbox = box.clone();
            int[][]dirs = new int[][]{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};//left, up, right, down;
            for(int[] dir: dirs){
                int[] next = new int[]{start[0]+dir[0], start[1]+dir[1]};
                if(used[next[0]][next[1]] || map[next[0]][next[1]] == '#'){
                    continue;
                }
                if(next[0] == box[0] && next[1] == box[1]){
                    curbox = new int[]{box[0]+dir[0], box[1]+dir[1]};
                    if(used[curbox[0]][curbox[1]] || map[curbox[0]][curbox[1]] == '#'){
                        continue;
                    }
                }

                used[next[0]][next[1]] = true;
                //System.out.println("next: "+Arrays.toString(next));
                int curLen = findWay(map, used, next, end, curbox, wayLen+1);
                used[next[0]][next[1]] = false;

                res = curLen == -1? res: Math.min(res, curLen);
            }
            return res == Integer.MAX_VALUE? -1: res;
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

#define MP make_pair
#define X first
#define Y second
using Coord = pair<int, int>;
using St = pair<Coord, Coord>;
using Maze = vector<vector<char>>;

St findPlayerAndBox(Maze &maze, int N, int M)
{
	Coord player, box;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			if (maze[i][j] == 'X')
				player = MP(i, j);
			if (maze[i][j] == '*')
				box = MP(i, j);
		}
	return MP(player, box);
}

Coord findBoxTarget(Maze &maze, int N, int M)
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (maze[i][j] == '@')
				return MP(i, j);
	return MP(0, 0);
}

vector<St> allPossibleOutcomes(Maze &maze, St state, int N, int M)
{
	St cur_st = state;
	Coord player = cur_st.X;
	Coord box = cur_st.Y;
	vector<St> result;
	// left
	if (player.Y - 1 == box.Y && player.X == box.X) { // box in the left
		if (box.Y >= 1 && maze[box.X][box.Y - 1] != '#') {
			Coord player_ = MP(player.X, player.Y - 1);
			Coord box_ = MP(box.X, box.Y - 1);
			result.push_back(MP(player_, box_));
		}
	} else if (player.Y - 1 >= 0 && maze[player.X][player.Y - 1] != '#') {
		Coord player_ = MP(player.X, player.Y - 1);
		result.push_back(MP(player_, box));
	}
	// right
	if (player.Y + 1 == box.Y && player.X == box.X) { // box in the right
		if (box.Y < M - 1 && maze[box.X][box.Y + 1] != '#') {
			Coord player_ = MP(player.X, player.Y + 1);
			Coord box_ = MP(box.X, box.Y + 1);
			result.push_back(MP(player_, box_));
		}
	} else if (player.Y < M - 1 && maze[player.X][player.Y + 1] != '#') {
		Coord player_ = MP(player.X, player.Y + 1);
		result.push_back(MP(player_, box));
	}
	// up
	if (player.X - 1 == box.X && player.Y == box.Y) { // box up
		if (box.X >= 1 && maze[box.X - 1][box.Y] != '#') {
			Coord player_ = MP(player.X - 1, player.Y);
			Coord box_ = MP(box.X - 1, box.Y);
			result.push_back(MP(player_, box_));
		}
	} else if (player.X >= 1 && maze[player.X - 1][player.Y] != '#') {
		Coord player_ = MP(player.X - 1, player.Y);
		result.push_back(MP(player_, box));
	}
	// down
	if (player.X + 1 == box.X && player.Y == box.Y) { // box below
		if (box.X < N - 1 && maze[box.X + 1][box.Y] != '#') {
			Coord player_ = MP(player.X + 1, player.Y);
			Coord box_ = MP(box.X + 1, box.Y);
			result.push_back(MP(player_, box_));
		}
	} else if (player.X < N - 1 && maze[player.X + 1][player.Y] != '#') {
		Coord player_ = MP(player.X + 1, player.Y);
		result.push_back(MP(player_, box));
	}
	return result;
}


int main(void)
{
	int N, M;
	cin >> N >> M;
	Maze maze;

	for (int i = 0; i < N; i++) {
		vector<char> row;
		for (int j = 0; j < M; j++) {
			char ch;
			cin >> ch;
			row.push_back(ch);
		}
		maze.push_back(row);
	}
	// (player, box)
	queue<St> q;
	map<St, int> steps;
	set<St> vis;

	St initial = findPlayerAndBox(maze, N, M);
	vis.insert(initial);
	steps.insert(MP(initial, 0));
	q.push(initial);
	Coord target_box = findBoxTarget(maze, N, M);

	while (!q.empty()) {
		St st = q.front();
		q.pop();
		for (St to_st : allPossibleOutcomes(maze, st, N, M)) {
			if (vis.find(to_st) == vis.end()) {
				q.push(to_st);
				steps.insert(MP(to_st, steps[st] + 1));
				vis.insert(to_st);
				if (to_st.Y == target_box) {
					cout << steps[to_st] << '\n';
					exit(0);
				}
			}
		}
	}
	cout << -1 << '\n';
	return 0;
}

#include <iostream>
#include <stdlib.h>
#include <memory.h>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <iterator>
#include <algorithm>
#include <limits.h>

using namespace std;

int N;
int M;
bool MAP[8][8];
int px, py;
int tx, ty;
int xx, xy;

int V[64][64];

inline int amin(int a, int b, int c, int d) {
	int i=(a<b?a:b);
	int j=(c<d?c:d);
	return i<j?i:j;
}

inline bool inrange(int x, int y){
	return x>=0 && x<N && y>=0 && y<M;	
}

bool con(int x1, int y1, int x2, int y2, int * len){
	if (x1==x2 && y1 == y2) {*len = 0; return true;}
	set<pair<int, int> > cur;
	set<pair<int, int> > tar;
	set<pair<int, int> > next;
	bool VISIT[8][8];
	for(int i=0;i<8;i++) for(int j=0;j<8;j++) VISIT[i][j] = false;

	int cnt= 0;
	bool reach = false;
	cur.insert(make_pair(x1, y1));
	tar.insert(make_pair(x2, y2));
	while(!cur.empty() && !tar.empty()) {
		set<pair<int, int> > *phead;
		set<pair<int, int> > *ptail;
		if (cur.size() > tar.size()) {phead = &tar; ptail = &cur;}
		else {phead = &cur; ptail = &tar;}

		next.clear();
		set<pair<int, int> >::iterator it;
		for(it=phead->begin();it!=phead->end();it++){
			pair<int, int> pos = *it;	
			if (ptail->find(pos)!=ptail->end()) {reach = true;break;}
			else {
				VISIT[pos.first][pos.second] = true;
				if (inrange(pos.first+1, pos.second) && !VISIT[pos.first+1][pos.second] && MAP[pos.first+1][pos.second]) {next.insert(make_pair(pos.first+1, pos.second));}// printf("\t-> <%d,%d>", pos.first+1, pos.second);}
				if (inrange(pos.first-1, pos.second) && !VISIT[pos.first-1][pos.second] && MAP[pos.first-1][pos.second]) {next.insert(make_pair(pos.first-1, pos.second));}// printf("\t-> <%d,%d>", pos.first-1, pos.second);}
				if (inrange(pos.first, pos.second+1) && !VISIT[pos.first][pos.second+1] && MAP[pos.first][pos.second+1]) {next.insert(make_pair(pos.first, pos.second+1));}// printf("\t-> <%d,%d>", pos.first, pos.second+1);}
				if (inrange(pos.first, pos.second-1) && !VISIT[pos.first][pos.second-1] && MAP[pos.first][pos.second-1]) {next.insert(make_pair(pos.first, pos.second-1));}// printf("\t-> <%d,%d>", pos.first, pos.second-1);}
			}
		}
		if (reach) break;
		else *phead = next;
		cnt+=1;
	}
	*len = cnt;
	return reach;
}

typedef pair<int, int>  Pos;
typedef pair<Pos, Pos> Pos_pair;
struct State
{
	Pos_pair pos;
	int len;
	friend bool operator < (const State &s1, const State &s2){
		if (s1.len < s2.len) return true;
		else return false;
	}
	friend bool operator > (const State &s1, const State &s2){
		if (s1.len > s2.len) return true;
		else return false;
	}
};

int bfs(){
	priority_queue<State, deque<State>, greater<State> > Q; // box<x,y> player<x,y>
	State init;
	init.pos = make_pair(make_pair(xx, xy), make_pair(px, py));
	init.len = 0;
	Q.push(init);
	MAP[xx][xy] = true;
	while(!Q.empty()) {
		State s = Q.top();
		Q.pop();

		Pos xpos = s.pos.first;
		Pos ppos = s.pos.second;
		int x = xpos.first;
		int y = xpos.second;
		px = ppos.first;
		py = ppos.second;
		MAP[x][y]=false;

		if (V[x*8+y][px*8+py]==-2) V[x*8+y][px*8+py]=-1;

		if (x == tx && y == ty) {return s.len;}
		int len = 0;
		//down
		if (inrange(x+1, y) && inrange(x-1, y) && MAP[x+1][y] && MAP[x-1][y] && V[(x+1)*8+(y)][(x)*8+(y)]==-2 && con(px, py, x-1, y, &len)) {
			State next_state;
			next_state.pos = make_pair(make_pair(x+1, y), make_pair(x, y));
			next_state.len = s.len + len+1;
			Q.push(next_state);
		}
		// up 
		if (inrange(x-1, y) && inrange(x+1, y) && MAP[x-1][y] && MAP[x+1][y] && V[(x-1)*8+(y)][(x)*8+(y)]==-2 &&con(px, py, x+1, y, &len)) {
			State next_state;
			next_state.pos = make_pair(make_pair(x-1, y), make_pair(x, y));
			next_state.len = s.len + len+1;
			Q.push(next_state);
		}
		// left
		if (inrange(x, y-1) && inrange(x, y+1) && MAP[x][y-1] && MAP[x][y+1] && V[(x)*8+(y-1)][(x)*8+(y)]==-2 && con(px, py, x, y+1, &len)) {
			State next_state;
			next_state.pos = make_pair(make_pair(x, y-1), make_pair(x, y));
			next_state.len = s.len + len+1;
			Q.push(next_state);
		}
		// right 
		if (inrange(x, y+1) && inrange(x, y-1) && MAP[x][y+1] && MAP[x][y-1] && V[(x)*8+(y+1)][(x)*8+(y)]==-2 && con(px, py, x, y-1, &len)) {
			State next_state;
			next_state.pos = make_pair(make_pair(x, y+1), make_pair(x, y));
			next_state.len = s.len + len+1;
			Q.push(next_state);
		}
		MAP[xpos.first][xpos.second]=true;
	}
	return -1;
}

int main() {
	while(cin>>N){
		cin>>M;
		if (N==0 || M==0) {cout<<0<<endl; continue;}
		for(int i=0;i<64;i++) for(int j=0;j<64;j++) V[i][j]=-2;
		string s;
		for(int i=0;i<N;i++){
			cin>>s;
			for(int j=0;j<M;j++) {
				if (s[j] == '.') MAP[i][j] = true;
				if (s[j] == '#') MAP[i][j] = false;
				if (s[j] == 'X') {MAP[i][j] = true; px=i;py=j;}
				if (s[j] == '@') {MAP[i][j] = true; tx=i;ty=j;}
				if (s[j] == '*') {MAP[i][j] = false; xx=i;xy=j;}
			}
		}
		cout<<bfs()<<endl;
	}
	return 0;
}