记录编号	439641	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2013]华容道	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.191 s
提交时间	2017-08-21 11:37:19	内存使用	3.46 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 101000
#define inf 0x3fffffff
using namespace std;
struct haha{
    int to,next,w;
}edge[N*2];
int head[N],cnt=1,n,m,qq,ji;
int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
int flag[50][50],shu[50][50][5],a[50][50];
void add(int u,int v,int w){
    edge[cnt].w=w;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
struct xixi{
    int x,y,step;
};
int bfs(int fx,int fy,int tx,int ty,int bx,int by){
    if(fx==tx&&fy==ty) return 0;
    memset(flag,0,sizeof(flag));
    queue<xixi> q;
    flag[fx][fy]=1;
    q.push((xixi){fx,fy,0});
    while(!q.empty()){
        int x,y,t;xixi temp=q.front();
        x=temp.x;y=temp.y;t=temp.step;
        q.pop();
        pos(k,0,3){
            if(a[x+xx[k]][y+yy[k]]&&(x+xx[k]!=bx||y+yy[k]!=by)&&flag[x+xx[k]][y+yy[k]]==0){
                if(x+xx[k]==tx&&y+yy[k]==ty) return t+1;
                q.push((xixi){x+xx[k],y+yy[k],t+1});
                flag[x+xx[k]][y+yy[k]]=1;
            }
        }
    }
    return inf;
}
int ex,ey,sx,sy,tx,ty;
int dis[N];
int spfa(){
    if(sx==tx&&sy==ty) return 0;
    pos(i,1,ji) dis[i]=inf;
    queue<int> q;
    pos(k,0,3)
        if(shu[sx][sy][k]){
            dis[shu[sx][sy][k]]=bfs(ex,ey,sx+xx[k],sy+yy[k],sx,sy);
            q.push(shu[sx][sy][k]);
        }
    while(!q.empty()){
        int temp=q.front();q.pop();
        for(int i=head[temp];i;i=edge[i].next){
            int to=edge[i].to;
            if(dis[to]>dis[temp]+edge[i].w){
                dis[to]=dis[temp]+edge[i].w;
                q.push(to);
            }
        }
    }
    int ans=inf;
    pos(k,0,3)
        if(shu[tx][ty][k])
            ans=min(ans,dis[shu[tx][ty][k]]);
    return ans==inf?-1:ans;
}
int main(){
    freopen("PuzzleNOIP2013.in","r",stdin);
    freopen("PuzzleNOIP2013.out","w",stdout);
    scanf("%d%d%d",&n,&m,&qq);
    pos(i,1,n) pos(j,1,m) scanf("%d",&a[i][j]);
    pos(i,1,n)
        pos(j,1,m)
            pos(k,0,3)
                if(a[i][j]&&a[i+xx[k]][j+yy[k]])
                    shu[i][j][k]=++ji;
    pos(i,1,n)
        pos(j,1,m)
            pos(k,0,3)
                if(shu[i][j][k])
                    add(shu[i][j][k],shu[i+xx[k]][j+yy[k]][k^1],1);
    pos(i,1,n)
        pos(j,1,m)
            pos(k,0,3)
                pos(l,0,3)
                    if(k!=l&&shu[i][j][k]&&shu[i][j][l])
                        add(shu[i][j][k],shu[i][j][l],bfs(i+xx[k],j+yy[k],i+xx[l],j+yy[l],i,j));
    while(qq--){
        scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
        printf("%d\n",spfa());
    }
    return 0;
}