题面
说实话这题看懂题面就做出来一半了，所以本题不提供简化题面
分析
题目描述很具有迷惑性，我们发现其实所谓“房门”的一系列操作，其实就是人物只能竖着走或者横着走。相当于我们要从左下角出发，一开始只能竖着走，图中分散着一些“节点”，人物只能在“节点”上才能改变方向，并付出一单位代价。
于是我们就发现，虽然题目中给了很大的一个矩形，但人物所有能走的路线其实就只有“节点”之间横竖相连的边。可以发现这些链接“节点”的边的数量其实只有 \(O(K)\)，我们完全可以把这些边连起来，转换为一个无向图最短路来处理。
赛时想到这就脑抽去写记忆化搜索了，直接T飞
但是，我们怎么处理”节点“上方向的改变呢，拆点就完事了。将点 \(p_i\) 分为 \(p_{i,0}\) 与 \(p_{i,1}\) 两个点，然后让竖边连接 \(p_{i,0}\leftrightarrow p_{j,0}\)，横边连接 \(p_{i,1}\leftrightarrow p_{j,1}\)，点自己到自己 \(p_{i,0}\leftrightarrow p_{i,1}\) 连接一条权值为 \(1\) 的边，跑 Dijkstra即可。需要额外注意的是这里起点与终点也算作特殊的“节点”，起点根据情况决定是否有自己到自己的边，终点永远没有自己到自己的边。令起点和终点分别 \(s\) 与 \(t\)，为由于题目要求初始是竖着走，所以答案即为 \(p_{s,0}\) 到 \(p_{t,0}\) 与 \(p_{t,1}\) 最短距离的最小值。
代码
这份代码是直接在之前记搜的基础上魔改的，常数较大
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void rd(T &x){
T res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
static char wtbuff[20];
static int wtptr;
if(x==0){
putchar('0');
}
else{
if(x<0){x=-x;putchar('-');}
wtptr=0;
while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
while(wtptr--) putchar(wtbuff[wtptr]);
}
if(endch!='\0') putchar(endch);
}
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,int> pli;
typedef pair<int,LL> pil;
const int MAXN=1e5+5,MAXK=2e5+5,MAX2K=MAXK<<1;
const LL INF=0x3f3f3f3f3f3f3f3f;
int m,n,k,delta,co[MAXK][2];
vector<int>line[2][MAXN];//0| 1-
vector<pil>g[MAX2K];
inline void add(int u,int v,LL w){
// cout<<u<<' '<<v<<' '<<w<<endl;
g[u].emplace_back(v,w);
g[v].emplace_back(u,w);
}
LL dis[MAX2K];
bitset<MAX2K>vis;
priority_queue<pli,vector<pli>,greater<pli> >pq;
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[0]=0;
pq.push(make_pair(dis[0],0));
int u,v;
while(!pq.empty()){
u=pq.top().second;pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto it:g[u]){
v=it.first;
if(dis[u]+it.second<dis[v]){
dis[v]=dis[u]+it.second;
pq.push(make_pair(dis[v],v));
}
}
}
}
inline bool cmp0(const int& a,const int& b){
return co[a][0]<co[b][0];
}
inline bool cmp1(const int& a,const int& b){
return co[a][1]<co[b][1];
}
int main(){
rd(m);rd(n);rd(k);
delta=k+2;
bool flag=0;
for(int i=1;i<=k;i++){
rd(co[i][0]);rd(co[i][1]);
if(co[i][0]==1 && co[i][1]==1){
flag=1;
continue;
}
if(co[i][0]==m && co[i][1]==n) continue;
line[0][co[i][0]].push_back(i);
line[1][co[i][1]].push_back(i);
add(i,i+delta,1);
}
co[0][0]=co[0][1]=1;line[0][1].push_back(0);line[1][1].push_back(0);
if(flag) add(0,0+delta,1);
co[k+1][0]=m;co[k+1][1]=n;line[0][m].push_back(k+1);line[1][n].push_back(k+1);
for(int i=1;i<=m;i++){
if(line[0][i].size()<=1) continue;
sort(line[0][i].begin(),line[0][i].end(),cmp1);
for(int j=1;j<line[0][i].size();j++){
add(line[0][i][j-1],line[0][i][j],abs(co[line[0][i][j-1]][1]-co[line[0][i][j]][1]));
}
line[0][i].clear();
}
for(int i=1;i<=n;i++){
if(line[1][i].size()<=1) continue;
sort(line[1][i].begin(),line[1][i].end(),cmp0);
for(int j=1;j<line[1][i].size();j++){
add(line[1][i][j-1]+delta,line[1][i][j]+delta,abs(co[line[1][i][j-1]][0]-co[line[1][i][j]][0]));
}
line[1][i].clear();
}
dijkstra();
// cout<<dis[1]<<' '<<dis[1+delta]<<endl;
LL ans=min(dis[k+1],dis[k+1+delta]);
if(ans==INF) puts("-1");
else wt(ans,'\n');
return 0;
}