也是一个很经典的优化最短路的题，感觉在暑假前集训做过类似思想的题来着
首先发现我们可以把所有有路灯的点以及终点看作关键点，很显然我们只关心关键点之间的边权以及最短路
不难发现对于两个关键点\(i,j\)，如果\(i,j\)相邻，则它们之间有边权为\(0\)的边；否则若\(|x_i-x_j|\le 2\or |y_i-y_j|\le 2\)，则它们之间有边权为\(1\)的边
暴力建图的话边数会比较炸，稍作观察后我们发现可以对每一行和每一列建立虚点\(H_i,C_i\)
对于某个关键点\((x,y)\)，向\(H_x,C_y\)连边权为\(1\)的边，再由\(H_{x+d},C_{y+D},d\in[-2,2]\)向该点连边权为\(0\)的边，不难发现这样的图和暴力\(k^2\)得到的图是等价的
因此跑个最短路即可，由于这里边权都是\(0/1\)，因此可以用0/1BFS解决
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=30005,INF=1e9,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,m,k,x,y,H[N],C[N],idx,tar,dis[N]; map <pi,int> lgt; vector <pi> v[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=k;++i)
scanf("%d%d",&x,&y),lgt[pi(x,y)]=++idx;
if (lgt.count(pi(n,m))) tar=lgt[pi(n,m)]; else tar=++idx;
for (i=1;i<=n;++i) H[i]=++idx;
for (i=1;i<=m;++i) C[i]=++idx;
for (auto [it,id]:lgt)
{
auto [x,y]=it; for (i=0;i<4;++i)
{
int nx=x+dx[i],ny=y+dy[i];
if (nx<1||nx>n||ny<1||ny>m) continue;
if (lgt.count(pi(nx,ny))) v[id].push_back(pi(lgt[pi(nx,ny)],0));
}
v[id].push_back(pi(H[x],1)); v[id].push_back(pi(C[y],1));
v[H[x]].push_back(pi(id,0)); v[C[y]].push_back(pi(id,0));
if (x!=1) v[H[x-1]].push_back(pi(id,0));
if (x>2) v[H[x-2]].push_back(pi(id,0));
if (x!=n) v[H[x+1]].push_back(pi(id,0));
if (x+2<=n) v[H[x+2]].push_back(pi(id,0));
if (y!=1) v[C[y-1]].push_back(pi(id,0));
if (y>2) v[C[y-2]].push_back(pi(id,0));
if (y!=m) v[C[y+1]].push_back(pi(id,0));
if (y+2<=m) v[C[y+2]].push_back(pi(id,0));
}
if (tar>k)
{
v[H[n]].push_back(pi(tar,0)); v[C[m]].push_back(pi(tar,0));
v[H[n-1]].push_back(pi(tar,0)); v[C[m-1]].push_back(pi(tar,0));
}
for (i=1;i<=idx;++i) dis[i]=INF; int st=lgt[pi(1,1)];
deque <int> dq; dq.push_front(st); dis[st]=0;
while (!dq.empty())
{
int now=dq.front(); dq.pop_front();
for (auto [to,w]:v[now]) if (dis[to]>dis[now]+w)
{
dis[to]=dis[now]+w;
if (w==0) dq.push_front(to); else dq.push_back(to);
}
}
return printf("%d",dis[tar]!=INF?dis[tar]:-1),0;
}