BOJ 2536

#include <iostream>
#include <queue>
using namespace std;

struct info{
    int x1;
    int y1;
    int x2;
    int y2;
    bool is_in(const int& x, const int& y)const{
        return (x>=x1 && x <= x2 && y >= y1 && y <= y2);
    }
    bool is_in(const info& a)const{
        return (a.x1 <=x2 && a.x2 >= x1 && a.y1<=y2 && a.y2 >= y1);
    }

};
void swap(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}
int visited[5001];
info bus[5001];
int M,N,K;
int sx,sy,dx,dy;
queue<int> q;
int bfs(){
    for (int i = 0; i <K ;i++){
        if (bus[i].is_in(sx,sy)) {
            q.push(i);
            visited[i] = 1;
        }
    }
    while (!q.empty()){
        int idx = q.front();
        if (bus[idx].is_in(dx,dy)){
            return visited[idx];
        }
        q.pop();
        for (int i = 0; i < K; i++){
            if (visited[i]) continue;
            if (bus[idx].is_in(bus[i])){
                visited[i] = visited[idx]+1;
                q.push(i);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> M >> N >> K;
    for (int i =0 ; i < K; i++){
        int num,x1,y1,x2,y2;
        cin >> num >> x1 >> y1 >> x2 >> y2;

        if (y1 > y2) swap(y1,y2);
        if (x1 > x2) swap(x1,x2);
        bus[i] = {x1,y1,x2,y2};
    }
    cin >> sx >> sy >> dx >> dy;
    cout << bfs()<<"\n";
    return 0;
}