首先，看到没有两座建筑有交，即不会形成一些封闭的凹型，所以在 $x$ 轴上一定可以不回头（感性理解），且不回头一定不劣，于是有一种简单的 dp，记 $f[i][j]$ 表示当走到坐标 $(i,j)$ 时的不算 $x$ 轴位移的最小代价，因为不回头，所以可以直接在最后 $+X$，转移的话，一种是直接从 $f[i-1][j]$ 转移得到，另一种是从 $f[i-1][j-1]+1$ 和 $f[i-1][j+1]+1$ 得到，这题不需要离散化，但校内模拟赛时是要的。

场上代码：

const ll inf=0x3f3f3f3f3f3f3f3f;
int n,x,V,B,q[maxn<<1],p[maxn<<1],tot,cnt,p0,q0,mx,mn,s[maxn],is[maxn];
ll g[maxn<<1];
struct rect
{
	int a,b,c,d;
}r[maxn];
vector<pair<int,int> >add[maxn],del[maxn];
void upd(int l,int r,int x){s[l+1]+=x,s[r]-=x;}
void init()
{
	int i;
	for(i=1;i<=V;++i)is[i]=s[i]+is[i-1];
}
void clear()
{
	int i;
	for(i=1;i<=V;++i)if(is[i])g[i]=inf;
}
int main()
{
	int i,j;
	n=read(),x=read();
	p[++tot]=0,q[++cnt]=0,q[++cnt]=x;
	for(i=1;i<=n;++i)
	{
		r[i].a=read(),r[i].b=read(),r[i].c=read(),r[i].d=read();
		if(r[i].a>r[i].c)swap(r[i].a,r[i].c);
		if(r[i].b<r[i].d)swap(r[i].b,r[i].d);
    --r[i].a,++r[i].c;
    --r[i].b,++r[i].d;
		q[++cnt]=r[i].a,q[++cnt]=r[i].c;
		p[++tot]=r[i].b,p[++tot]=r[i].d;
		if(r[i].b*r[i].d<=0)mx=max(mx,r[i].b),mn=min(r[i].d,mn);
	}
	sort(p+1,p+tot+1),V=unique(p+1,p+tot+1)-p-1;
	sort(q+1,q+cnt+1),B=unique(q+1,q+cnt+1)-q-1;
	p0=lower_bound(p+1,p+V+1,0)-p,q0=lower_bound(q+1,q+B+1,0)-q;
	for(i=1;i<=n;++i)
	{
		r[i].a=lower_bound(q+1,q+B+1,r[i].a)-q,r[i].c=lower_bound(q+1,q+B+1,r[i].c)-q;
		r[i].b=lower_bound(p+1,p+V+1,r[i].b)-p,r[i].d=lower_bound(p+1,p+V+1,r[i].d)-p;
		add[r[i].a].push_back({r[i].d,r[i].b});
		del[r[i].c].push_back({r[i].d,r[i].b});
	}
	memset(g,63,sizeof(g));
	g[p0]=0;
	for(i=1;i<=V;++i)g[i]=min(g[i-1]+p[i]-p[i-1],g[i]);
	for(i=V;i;--i)g[i]=min(g[i+1]+p[i+1]-p[i],g[i]);
	for(auto nw:add[q0])upd(nw.first,nw.second,1);
	for(auto nw:del[q0])upd(nw.first,nw.second,-1);
	init();
	clear();
	for(i=2;i<=B;++i)
	{
		for(j=1;j<=V;++j)g[j]=min(g[j],g[j-1]+p[j]-p[j-1]);
		for(j=V;j;--j)g[j]=min(g[j],g[j+1]+p[j+1]-p[j]);	
		for(auto nw:add[i])upd(nw.first,nw.second,1);
		for(auto nw:del[i])upd(nw.first,nw.second,-1);
		init();
		clear();
	}
	printf("%lld\n",g[p0]+x);
	return 0;
}

正解可以通过这个 dp 来推广，我们有一种贪心策略：当一个位置没有被建筑物阻挡时，直接向前走，被阻挡时再向两侧绕，这样显然不劣，所以对于每个 $i$ 只有被障碍物阻挡的 $f[i][j]$ 需要特殊处理，其他位置直接继承，而处理后每个建筑物至多增加两个关键点，原本的关键点只要被特殊处理过一次就会被消掉，所以我们用一个 set 来维护关键点，每次找到被覆盖的所有关键点，更新建筑物两侧的 $f[i][j]$，再重新加回 set 中，总复杂度均摊下来是 $O(n \log n)$ 的。

#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
#define ll long long
#define frp freopen
#define fio(in,out) frp(in,"r",stdin),frp(out,"w",stdout)
inline void bug(){cout<<endl;}
template<typename TS,typename ... T>
inline void bug(TS p,T ... x){cout<<p<<" ";bug(x...);}
template<class T=int>
inline T read()
{
	T res=0,f=1;char c;
	for(;(c=getchar())<'0' || c>'9';c=='-'?f=-f:0);
	while(c>='0' && c<='9')res=(res<<3)+(res<<1)+(c^48),c=getchar();
	return res*f;
}
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,X,Y;
ll ans;
struct rect
{
	int a,b,c,d;
	bool operator<(const rect &x)const{
		return a<x.a;
	}
}r[maxn];
vector<pair<int,ll> >t;
set<pair<int,ll> >s;
int main()
{
	int i;
//	fio("short.in","short.out");
	X=read(),Y=read(),n=read();
	s.insert({0,0});
	for(i=1;i<=n;++i)
	{
		r[i].a=read(),r[i].b=read(),r[i].c=read(),r[i].d=read();
		if(r[i].a>r[i].c)swap(r[i].a,r[i].c);
		if(r[i].b>r[i].d)swap(r[i].b,r[i].d);
		--r[i].a,--r[i].b,++r[i].d;
	}
	sort(r+1,r+n+1);
	for(i=1;i<=n&&r[i].a<X;++i)
	{
		if(r[i].a!=r[i-1].a){
			for(auto v:t)s.insert(v);
			t.clear();
		}
		ll f1=inf,f2=inf;
		auto l=s.lower_bound({r[i].b,0});
		auto e=s.lower_bound({r[i].d+1,0});
		for(auto it=l;it!=e;++it)
			f1=min(f1,it->second+abs(r[i].b-it->first)),
			f2=min(f2,it->second+abs(r[i].d-it->first));
		t.push_back({r[i].b,f1});
		t.push_back({r[i].d,f2});
		s.erase(l,e);
	}
	ans=inf;
	for(auto v:t)s.insert(v);
	for(auto v:s)ans=min(ans,v.second+abs(Y-v.first));
	printf("%lld",ans+X);
	return 0;
}

一个小 case，注意有一些建筑物的横坐标大于 $X$，这一部分直接 break 掉。