Noip2013day2 finale title Huarong Road

题链接 First of all, this is a poisonous tumor problem. I wrote it in the afternoon and didn't make it out. After reading the solution, I realized that is all nonsense

分析

I started thinking about 70 points of violence, directly Violent BFS, the answer is offline, the starting point is the same; try more than 70 points   First of all, it is easy to see that this is a graph topic, obviously it is to use the shortest path, determine the d array state d[i][j][k] indicates the starting point to (i,j),k The direction is the shortest path of the white block, but due to the characteristics of the map, the construction of the map seems to be a little ghost, 死磕2 hours nothing, so decisive to understand the problemThere is a feature that the moving piece is actually moving White block   If the grid S wants to go to the grid in the k direction (left, right, up, down) adjacent to it, it must first move the cost of the E grid through w to a grid, and then let S go with the cost of 1 When I get there, the total cost is w+1. Since the cost of taking one step from one grid to the adjacent direction is used multiple times, we preprocess it into an array a[x][y][k][h], Represents the least cost of the (x, y) piece, the white plaid in the k direction, and the piece going to the adjacent grid in the h direction. This can be preprocessed with BFS.   Then there is the process of the shortest path, templating, the data can be used with spfa, okay, I am too lazy to write DijkstraThe answer is just processed first. The code is accompanied by a comment.

#include<bits/stdc++.h>
#define up 1
#define down 2
#define left 3
#define right 4// Direction
#define N 35
#define inf 0x3f3f3f3f
using namespace std;
struct node{int x,y,k;};//点点
int p[N][N],d[N][N][5],Ex,Ey,a[N][N][5][5],deep[N][N],n,m;
bool in[N][N][5],done[N][N];
queue<node>q,qb;
int other(int k){
    if(k==up)return down;
    if(k==down)return up;
    if(k==left)return right;
    if(k==right)return left;
} // Reverse direction movementnode go(node ​​n,int k){
    node t=n;
    if(k==up)t.x--;
    if(k==down)t.x++;
    if(k==left)t.y--;
    if(k==right)t.y++;
    return t;
} //Mobile chess piece 
int bfs(node s,node t){
    if(p[s.x][s.y]==0||p[s.x][s.y]==0)return inf;//If two points There is a fixed point, you can not reach 
    memset(deep,0x3f,sizeof(deep));
    memset(done,0,sizeof(done));
    qb=*(new queue<node>);// empty queue is very important <s> is pit</s>qb.push(s);
    Deep[sx][sy]=0;done[s.x][s.y]=true;
    while(!qb.empty()&&!done[t.x][t.y]){
        node u=qb.front();
        qb.pop();
        for(int k=1;k<=4;k++){
            node v=go(u,k);
            if(!done[v.x][v.y]&&p[v.x][v.y]==1){
                done[v.x][v.y]=true;
                qb.push(v);
                deep[v.x][v.y]=deep[u.x][u.y]+1;
            }
        }
    }
    return deep[t.x][t.y];
}//Basic wide search operation 
void init(){
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(p[i][j]==0)continue;
            p[i][j]=0;//Close the point to prevent redundant BFS
            for(int k=1;k<=4;k++){
                for(int h=1;h<=4;h++){
                    if(h<k){
                        a[i][j][k][h]=a[i][j][h][k];
                        continue;
                    }//According to symmetry, speed up efficiencynode T1=go((node){i,j},k);
                    Node t2=go((node){i,j},h);if(p[t1.x][t1.y]==0||p[t2.x][t2.y]==0)continue;//Judge fixed pointa[i][j][k][h]=bfs(t1,t2)+ 1;//w+1 operation}
            }
            p[i][j]=1;//Recovery point connection}
}int spfa(node S,node T){
    if(S.x==T.x&&S.y==T.y)return 0;
    memset(d,0x3f,sizeof(d));
    memset(in,0,sizeof(in));
    q=*(new queue<node>);
    if(p[S.x][S.y]==0||p[T.x][T.y]==0)return inf;
    p[S.x][S.y]=0;
    for(int k=1;k<=4;k++){
        q.push((node){S.x,S.y,k});
        in[S.x][S.y][k]=true;
        d[S.x][S.y][k]=bfs((node){Ex,Ey},go(S,k));//Steps to calculate the white grid to the starting point}//Queue initializationp[Sx][Sy]=1;
    while(!q.empty()){
        node u=q.front();
        q.pop();
        in[u.x][u.y][u.k]=false;
        for(int h=1;h<=4;h++){
            node v=go(u,h);
            v.k=other(h);// Reverse position 
            if(d[u.x][u.y][u.k]+a[u.x][u.y][u.k][h]<d[v.x][v.y][v.k]){
                d[v.x][v.y][v.k]=d[u.x][u.y][u.k]+a[u.x][u.y][u.k][h];
                if(!in[v.x][v.y][v.k]){
                    q.push(v);
                    in[v.x][v.y][v.k]=true;
                }
            }//Execute slack operation}
    }int res=inf;
    for(int k=1;k<=4;k++)
        res=min(res,d[T.x][T.y][k]);//Get the answer 
    return res;
}
int main(){
    int Q,sx,sy,tx,ty;
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&p[i][j]);
    init();//Preprocess 
    for(int i=1;i<=Q;i++){
        scanf("%d%d%d%d%d%d",&Ex,&Ey,&sx,&sy,&tx,&ty);
        int ans=spfa((node){sx,sy},(node){tx,ty});
        if(ans<inf)printf("%d\n",ans);
        else printf("-1\n");
    }//Online operation
    return 0;
}