80pts

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

#include<bits/stdc++.h>
using namespace std;
const int N=35;
struct Node{
    int a,b,c,d;
};
int dist[N][N][N][N];
int g[N][N];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int n,m,k;
int bfs(int a,int b,int c,int d,int e,int f)
{
    queue<Node> q;
    dist[a][b][c][d]=0;
    q.push({a,b,c,d});
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t.c==e&&t.d==f)
        {
            return dist[t.a][t.b][t.c][t.d];
        }
        for(int i=0;i<4;i++)
        {
            int a=t.a+dx[i],b=t.b+dy[i];
            if(a<1||a>n||b<1||b>m||!g[a][b]) continue;
            int na,nb,nc,nd;
            if(a==t.c&&b==t.d) //和箱子进行交换
            {
                na=t.c,nb=t.d,nc=t.a,nd=t.b;
            }
            else //箱子不动,人动
            {
                na=a,nb=b,nc=t.c,nd=t.d;
            }
            if(dist[na][nb][nc][nd]>dist[t.a][t.b][t.c][t.d]+1)
            {
                dist[na][nb][nc][nd]=dist[t.a][t.b][t.c][t.d]+1;
                q.push({na,nb,nc,nd});
            }
        }
    }
    return -1;
}
int main()
{
   
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
    for(int i=1;i<=k;i++)
    {
        int a,b,c,d,e,f;
        cin>>a>>b>>c>>d>>e>>f;
        memset(dist,0x3f,sizeof dist);
        cout<<bfs(a,b,c,d,e,f)<<endl;
    }
    return 0;
}

100pts

首先需要从起点移动到起点箱子旁边，然后把箱子移动和人在箱子的周边的不同位置看成不同的状态,最后从起点到终点做一遍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;
}