rt，思路建虚点+最短路，时间复杂度 $\mathcal{O}(nm)$，但是空间被卡了

#include<bits/stdc++.h>
#define N 3005
using namespace std;
int n,m,k,a[N][N],h[N*N],dis[N*N<<1],tot,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
deque<int>q;
struct edge{
    int v,w;
};
vector<edge>g[N*N<<1];
int id(int x,int y){
    return (x-1)*m+y;
}
int main(){
    memset(dis,-1,sizeof dis);
    scanf("%d%d%d",&n,&m,&k);
    tot=n*m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1,x,y;i<=k;++i){
        scanf("%d%d",&x,&y);
        if(!h[a[x][y]]){
            g[h[a[x][y]]=++tot].push_back({0,1});
            g[0].push_back({tot,0});
        }
        g[id(x,y)].push_back({h[a[x][y]],1});
        g[h[a[x][y]]].push_back({id(x,y),0});
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(a[i][j]){
                for(int l=0;l<4;++l){
                    int u=i+dx[l],v=j+dy[l];
                    if(u&&u<=n&&v&&v<=m&&a[u][v]){
                        g[id(i,j)].push_back({id(u,v),1});
                    }
                }
            }
        }
    }
    dis[1]=0;
    q.push_back(1);
    while(q.size()){
        int u=q.front();
        q.pop_front();
        for(auto[v,w]:g[u]){
            if(~dis[v]){
                continue;
            }
            dis[v]=dis[u]+w;
            if(w){
                q.push_back(v);
            }else{
                q.push_front(v);
            }
        }
    }
    printf("%d\n",dis[id(n,m)]);
}