拆点 暴搜
#include<bits/stdc++.h>
using namespace std;
const int N = 110,M=10000;
bool st[N][N][M];
int n,m,t;
int dist[N][N];
typedef pair<int, pair<int,int>> PII;
#define x first
#define y second
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(){
queue<PII> q;
q.push({0,{1,1}});
memset(dist,0x3f,sizeof dist);
dist[1][1]=0;
while(q.size()){
auto t=q.front();q.pop();
int time=t.x,r=t.y.x,c=t.y.y;
if(st[r][c][time]) continue;
st[r][c][time]=true;
for(int i=0;i<4;i++){
int x=r+dx[i],y=c+dy[i];
if(x==n&&y==m){
dist[x][y]=time+1;
return;
}
if(x<1||x>n||y>m||y<1||st[x][y][time+1]) continue;
dist[x][y]=time+1;
q.push({time+1,{x,y}});
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
while(t--){
int r,c,a,b;
scanf("%d%d%d%d",&r,&c,&a,&b);
for(int i=a;i<=b;i++){
st[r][c][i]=true;
}
}
bfs();
cout<<dist[n][m];
return 0;
}