做法

分层图胎教题。

除 $(1,1)$ 和 $(n,m)$ 外，只用考虑按钮的位置即可。

考虑分层图，按钮可以通过 $1$ 的代价切换所在层。然后竖着的边都建在一层，横着的边都建在一层。

注意开头和结尾如果没有按钮要额外增加点，且如果是没有按钮的开头结尾点是不能建连接上下层图的边的。

相当于所在的分层图代表了当前局面门的状态，在按钮节点可以切换状态（切换层）。

按钮之间的边权就是距离。

注意！

如果你在 LOJ 上过了，AT 上全 Wa。请在输出的位置加上换行！

代码

::::success[Accepted code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10;
int n,m,T,ind[N];
struct S{
	int x,y,id;
}f[N];
bool vis[N];
vector<pair<int,int> >x[N],y[N],G[N];
int dis[N];//到点i 
signed main()
{
//	freopen("sample.in","r",stdin);
//	freopen("9.in","r",stdin);
//	freopen("modern.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>T;
	int s=0,t=0;
	int num=T+2;
	for(int i=1;i<=T;i++)
	{
		cin>>f[i].x>>f[i].y;
		if(f[i].x==1 && f[i].y==1)s=i;	
		if(f[i].x==n && f[i].y==m)t=i;	
		x[f[i].x].push_back({f[i].y,i});
		y[f[i].y].push_back({f[i].x,i});
		f[i].id=i;
		G[i].push_back({i+num,1});
		G[i+num].push_back({i,1});
	}
	if(!s)
	{
		f[T+1].x=1;
		f[T+1].y=1;
		x[1].push_back({1,T+1});
		y[1].push_back({1,T+1});
	}
	if(!t)
	{
		f[T+2].x=n;
		f[T+2].y=m;
		x[n].push_back({m,T+2});
		y[m].push_back({n,T+2});
	}
	
	for(int i=1;i<=n;i++)
	{
		sort(x[i].begin(),x[i].end());
		if(x[i].size()>1)
		{
			for(int j=1;j<x[i].size();j++)
			{
				G[x[i][j].second].push_back({x[i][j-1].second,x[i][j].first-x[i][j-1].first});
				G[x[i][j-1].second].push_back({x[i][j].second,x[i][j].first-x[i][j-1].first});
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		sort(y[i].begin(),y[i].end());
		if(y[i].size()>1)
		{
			for(int j=1;j<y[i].size();j++)
			{
				G[y[i][j].second+num].push_back({y[i][j-1].second+num,y[i][j].first-y[i][j-1].first});
				G[y[i][j-1].second+num].push_back({y[i][j].second+num,y[i][j].first-y[i][j-1].first});
			}
		}
	} 
	memset(dis,0x3f,sizeof dis);
	queue<int>q;
	if(!s)
	{
		dis[T+1]=0;
		q.push(T+1);
	}
	else 
	{
		dis[s]=0;
		q.push(s);
	}
	while(q.size())
	{
		int u=q.front();
		vis[u]=1;
		q.pop();
		for(auto i:G[u])
		{
			int v=i.first;
			int w=i.second;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push(v);
			}
		}
	}
	if(!t)
	{	
		if(!(vis[T+2+num]||vis[T+2]))cout<<"-1\n";
		else cout<<min(dis[T+2+num],dis[T+2])<<"\n";
	}
	else
	{
		if(!(vis[t+num]||vis[t]))cout<<"-1\n";
		else cout<<min(dis[t],dis[t+num])<<"\n";
	}
	return 0;
}

::::