(30^4*500)

直接使用4维bfs进行搜索，第一次箱子走到终点位置的时候结束搜索

#include<bits/stdc++.h>
using namespace std;
const int N=35,INF=0x3f3f3f3f;
struct node{
    int mx,my,nx,ny;//空格的位置，初始棋子现在的位置
    int stp;//步数 
};
int n,m,q;
int mp[N][N];
queue<node>Q;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
bool vis[N][N][N][N];
bool check(int xx,int yy)
{
    if(xx<0||xx>n||yy<0||yy>m||mp[xx][yy]==0) return 0;
    return 1;
}
int main() 
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    while(q--)
    {
        int ex,ey,sx,sy,tx,ty;
        cin>>ex>>ey>>sx>>sy>>tx>>ty;
        if(sx==tx&&sy==ty)
        {
            puts("0");//起点和终点一样 
            continue; 
        }
        memset(vis,0,sizeof(vis));
        bool flag=0;
        while(!Q.empty()) Q.pop();
        node s;
        s.mx=ex,s.my=ey,s.nx=sx,s.ny=sy,s.stp=0;
        vis[ex][ey][sx][sy]=1;
        Q.push(s);
        while(!Q.empty())
        {
            s=Q.front();
            Q.pop();
            for(int i=0;i<4;i++)
            {
                node nxt;
                nxt.mx=s.mx+dx[i],nxt.my=s.my+dy[i];
                if(!check(nxt.mx,nxt.my)) continue; //人越界了
                if(nxt.mx==s.nx&&nxt.my==s.ny) nxt.nx=s.mx,nxt.ny=s.my; //人和箱子交换
                else nxt.nx=s.nx,nxt.ny=s.ny; //人走到下一个位置
                nxt.stp=s.stp+1; //步数增加一个
                if(nxt.nx==tx&&nxt.ny==ty) //箱子走到了对应位置
                {
                    flag=1;
                    printf("%d\n",nxt.stp);
                    break;
                }
                if(vis[nxt.mx][nxt.my][nxt.nx][nxt.ny]) continue; //已经走过了
                Q.push(nxt); //继续遍历后面的点
                vis[nxt.mx][nxt.my][nxt.nx][nxt.ny]=1; //标记这个状态已经走过
            }
            if(flag) break;
        }
        if(flag) continue;
        else puts("-1");
    }
    return 0;
}

($bfs(900^2*4)+spfa(900*4*4*500)$)

首先需要从起点移动到起点箱子旁边，然后把箱子移动和人在箱子的周边的不同位置看成不同的状态,最后从起点到终点做一遍spfa即可。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=35,M=3610,K=M*4,INF=0x3f3f3f3f;
int n,m,q;
int g[N][N];
int h[M],e[K],w[K],ne[K],idx;
int dist1[N][N],dist2[M];
bool st[M];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int get(int x,int y,int z) //3维映射成一维
{
    return ((x-1)*m+y-1)*4+z;
}
void bfs(int px,int py,int bx,int by,int dir) //计算(px,py)到(bx,by)的距离
{
    queue<PII> q;
    memset(dist1,0x3f,sizeof dist1);
    dist1[px][py]=dist1[bx][by]=0;
    q.push({px,py});
    while(q.size()) //处理(px,py)可以到的所有点
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.x+dx[i],y=t.y+dy[i];
            if(g[x][y]&&dist1[x][y]>dist1[t.x][t.y]+1)
            {
                dist1[x][y]=dist1[t.x][t.y]+1;
                q.push({x,y});
            }
        }
    }
    if(dir==-1) return ; //只需要走到箱子的方向
    int id=get(bx,by,dir);
    for(int i=0;i<4;i++) //建立走到箱子的其它位置的边
    {
        if(i!=dir)
        {
            int x=bx+dx[i],y=by+dy[i];
            if(dist1[x][y]<INF)
            {
                add(id,get(bx,by,i),dist1[x][y]);
            }
        }
    }
    add(id,get(px,py,dir^2),1); //和箱子进行交换
}
int spfa(int sx,int sy,int tx,int ty) ///从起点走到终点
{
    queue<int> q;
    memset(dist2,0x3f,sizeof dist2);
    for(int i=0;i<4;i++) //一共有4个状态可能作为起点
    {
        int x=sx+dx[i],y=sy+dy[i];
        if(dist1[x][y]<INF)
        {
            int k=get(sx,sy,i);
            dist2[k]=dist1[x][y];
            q.push(k);
            st[k]=true;
        }
    }
    while(q.size()) //spfa搜索
    { 
        auto t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist2[j]>dist2[t]+w[i])
            {
                dist2[j]=dist2[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    int res=INF;
    for(int i=0;i<4;i++) //枚举终点
    {
        res=min(res,dist2[get(tx,ty,i)]);
    }
    if(res==INF) res=-1;
    return res;
}

int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) //预处理每种状态
    {
        for(int j=1;j<=m;j++)
        {
            if(g[i][j])
            {
                for(int k=0;k<4;k++)
                {
                    int x=i+dx[k],y=j+dy[k];
                    if(g[x][y])
                    {
                        bfs(x,y,i,j,k);
                    }
                }
            }
        }
    }
    while(q--)
    {
        int ex,ey,sx,sy,tx,ty;
        cin>>ex>>ey>>sx>>sy>>tx>>ty;
        if(sx==tx&&sy==ty)
        {
            cout<<0<<endl;
        }
        else
        {
            bfs(ex,ey,sx,sy,-1);
            cout<<spfa(sx,sy,tx,ty)<<endl;
        }
    }
    return 0;
}