#include using namespace std; #include using namespace atcoder; using ll = long long; #define all(x) (x).begin(), (x).end() template ostream &operator<<(ostream &os, const pair &p) { os << p.first << ' ' << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { ll s = (ll)v.size(); for (ll i = 0; i < s; i++) os << (i ? ' ' : ' ') << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } //エラトステネスのふるい bool IsPrime(ll num) { if (num < 2) return false; else if (num == 2) return true; else if (num % 2 == 0) return false; // 偶数はあらかじめ除く double sqrtNum = sqrt(num); for (int i = 3; i <= sqrtNum; i += 2) { if (num % i == 0) { // 素数ではない return false; } } // 素数である return true; } // map,bool> mp; // rep(i,m) { // mp[make_pair(x[i],y[i])]=true; // } #define rep(i, n) for (ll (i) = 0; (i) < (ll)(n); (i)++) int main() { ll h,w,n; cin >> h >> w >> n; vector a(n); vector b(n); vector c(n); vector d(n); map,ll> fmp; map,ll> smp; map,bool> bmp; rep(i,n) { cin >> a[i] >> b[i] >> c[i] >> d[i]; fmp[make_pair(a[i],b[i])]=c[i]; smp[make_pair(a[i],b[i])]=d[i]; bmp[make_pair(a[i],b[i])]=true; } queue> q; vector> mint(h,vector(w,1e18)); mint[0][0]=0; q.push(make_pair(1,1)); while(!q.empty()) { ll f=q.front().first; ll s=q.front().second; q.pop(); if (f-1>0&&mint[f-2][s-1]==1e18) { q.push(make_pair(f-1,s)); mint[f-2][s-1]=min(mint[f-2][s-1],mint[f-1][s-1]+1); } if (h-1>=f&&mint[f][s-1]==1e18) { q.push(make_pair(f+1,s)); mint[f][s-1]=min(mint[f][s-1],mint[f-1][s-1]+1); } if (s-1>0&&mint[f-1][s-2]==1e18) { q.push(make_pair(f,s-1)); mint[f-1][s-2]=min(mint[f-1][s-2],mint[f-1][s-1]+1); } if (w-1>s&&mint[f-1][s]==1e18) { q.push(make_pair(f,s+1)); mint[f-1][s]=min(mint[f-1][s],mint[f-1][s-1]+1); } if (bmp[{f-1,s-1}]&&mint[f-1][s]!=1e18) { q.push({fmp[{f-1,s-1}],smp[{f-1,s-1}]}); mint[fmp[{f-1,s-1}]][smp[{f-1,s-1}]]=min(mint[fmp[{f-1,s-1}]][smp[{f-1,s-1}]],mint[f-1][s-1]+1); } } cout << mint[h-1][w-1] << endl; }