Anonymous

#include <iostream>
#include <queue>

using namespace std;

char map[2000][2000];
int dp[2000][2000];
int n;
int ox, oy, hx, hy;
int dx, dy;
queue<int> answers;
bool foundpath;
char dir;
int bestdistance = INT_MAX;

void north(){ dx = 0; dy = 1; dir = 'n';}
void south(){ dx = 0; dy = -1; dir = 's';}
void east(){ dx = 1; dy = 0; dir = 'e';}
void west(){ dx = -1; dy = 0; dir = 'w';}

void print(int x1, int x2, int y1, int y2){
    for(int i = y2; i >= y1; i--){
        for(int j = x1; j <= x2; j++){
            cout << map[i][j];    
        }    
        cout << endl;
    }
}

int solve();

int main(){
    
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        memset(map, '.', sizeof map);
        memset(dp, INT_MAX/2, sizeof dp);
        foundpath = false;
        bestdistance = INT_MAX;
        int ans = solve();
        //cout << foundpath << endl;
        if(!foundpath){
            ans = 0;
        }
        answers.push(ans);
    }

    while(answers.size() > 0){
        int x = answers.front();
        answers.pop();
        if(x > 0){
            cout << x << endl;    
        } else{
            cout << "No Path" << endl;    
        }
    }
    
    //system("pause");
    return 0;
}


int go(int x, int y, int steps){
    if(x < 0 || y <0) return INT_MAX/2;
    if(x >= 2000 || y >= 2000) return INT_MAX/2;
    
    if(map[y][x] != '.'){
        //cout << map[y][x] << " " << y-1000 << " " << x-1000 << endl;
    }
    
    if(map[y][x] == 'V') return INT_MAX;
    if(dp[y][x] + steps > bestdistance && dp[y][x] != INT_MAX/2) return dp[y][x];
    char orig = map[y][x];
    map[y][x] = 'V';
    
    if(orig == 'L'){
        if(dir != 'e'){
            west();
            dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        }
        north();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        if(y-1000 == 8){
            //print(1000, 1010, 1003, 1012);    
        }
        south();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
    }
    if(orig == 'R'){
        if(dir != 'w'){
            east();
            dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        }
        north();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        south();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
    }
    if(orig == 'B'){
        if(dir != 'n'){
            south();
            dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        }
        east();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        west();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
    }
    if(orig == 'T'){
        if(dir != 's'){
            north();
            dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        }
        east();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        west();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
    }
    if(orig == 'C'){
        east();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        south();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        north();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
        west();
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
    }
    
    if(orig == 'H'){
        //cout << "DONE " << steps << endl;
        //print(1000, 1010, 1003, 1012);
        if(steps < bestdistance){
            bestdistance = steps;
            foundpath = true;    
        }
        dp[y][x] = 0;
    }
    if(orig == 'O' || orig == '.'){
        dp[y][x] = min(dp[y][x], go(x+dx, y+dy, steps+1));
    }
    
    map[y][x] = orig;
    return dp[y][x]+1;
}

int solve(){
    cin >> ox >> oy >> hx >> hy;
    ox += 1000;
    oy += 1000;
    hx += 1000;
    hy += 1000;
    map[oy][ox] = 'O';
    map[hy][hx] = 'H';
    cin >> n;
    for(int i = 0; i < n; i++){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;    
        x1 += 1000;
        x2 += 1000;
        y1 += 1000;
        y2 += 1000;
        
        if(x1 > x2)
            swap(x1, x2);
        if(y1 > y2)
            swap(y1, y2);
            
        for(int i = x1+1; i <= x2; i++){
            map[y1][i] = 'B';
            map[y2][i] = 'T';
        }
        for(int i = y1+1; i <= y2; i++){
            map[i][x1] = 'L';
            map[i][x2] = 'R';
        }
        map[y1][x1] = map[y1][x2] = map[y2][x1] = map[y2][x2] = 'C';
        for(int i = x1+1; i < x2; i++){
            for(int j = y1+1; j < y2; j++){
                map[j][i] = '*';    
                //cout << j << " " << i << endl;
            }    
        }
        
        //print(x1-5, x2+5, y1-5, y2+5);
    }
    
    north();
    go(ox, oy, 0);
    south();
    go(ox, oy, 0);
    east();
    go(ox, oy, 0);
    west();
    go(ox, oy, 0);
    
    return bestdistance;
}