链式前向星 + dijsktra

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
/*

*/
struct Node{
	int x,y,cnt;
	bool operator>(const Node&x)const {return x.cnt>cnt; }
};
int n,m,headx[N],edgex[N],lastx[N],heady[N],edgey[N],lasty[N],idx;
void addx(int u,int v){edgex[++idx]=v,lastx[idx]=headx[u],headx[u]=idx;}
void addy(int u,int v){edgey[++idx]=v,lasty[idx]=heady[u],heady[u]=idx;}
bool visx[N],visy[N];
int dijsktra(){
	priority_queue<Node,vector<Node>,greater<Node> > pq;
	pq.push({1,0,0});
	while(!pq.empty()){
		Node t=pq.top(); pq.pop();
		if(t.x==n) return cout<<t.cnt,0;
		if(!visx[t.x]){
			visx[t.x]=1;
			for(int i=headx[t.x];i;i=lastx[i]) if(!visy[edgex[i]]) pq.push({t.x,edgex[i],t.cnt+1});
		}
		if(!visy[t.y]){
			visy[t.y]=1;
			for(int i=heady[t.y];i;i=lasty[i]) if(!visx[edgey[i]]) pq.push({edgey[i],t.y,t.cnt+1});
		}
		
	}
	cout<<-1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='#') addx(i,j),addy(j,i);
		}
	}
	dijsktra();
	return 0;
}