双向广搜解法

双向广搜：
顾名思义，就是一边从头搜，一边从尾搜
它可以减少时间复杂度，但有几率增加空间复杂度

先初始化和输入 （这步不用教吧）

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct node{
	int x,y;
};
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
int n,m,v1[45][45],v2[45][45];
char g[45][45];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
		}
	}
	cout<<bfs();
}

接下来，由于要两边一起来，所以要弄2个队列（q1,q2)和2个标记数组(v1,v2（在上面）)

int bfs(){
	memset(v1,-1,sizeof v1);
	memset(v2,-1,sizeof v2);
	queue<node> q1,q2;
	q1.push({1,1});
	q2.push({n,m});
	v1[1][1]=0;
	v2[n][m]=0;
}

然后就是本解法的华点：
当两边有一端无路可走时，就结束了
然后，优先解决队列中较多的那一头
剩下的就和正常广搜一样了

while(q1.size() && q2.size()){//有一边走不到就不行 
		if(q1.size()>q2.size()){//先执行q1 
			node n1=q1.front();
			q1.pop();
			for(int i=0;i<4;i++){
				int xx=n1.x+dx[i];
				int yy=n1.y+dy[i];
				if(xx>=1 && xx<=n && yy>=1 && yy<=m && g[xx][yy]!='#' && v1[xx][yy]==-1){
					q1.push({xx,yy});
					v1[xx][yy]=v1[n1.x][n1.y]+1;
					if(v2[xx][yy]!=-1)return v1[xx][yy]+v2[xx][yy]+1;//相遇 
				}
			} 
		}
		else{
              ……
        }

最后，献上完整代码，请勿直接搬运，抄袭可耻

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct node{
	int x,y;
};
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
int n,m,v1[45][45],v2[45][45];
char g[45][45];
int bfs(){
	memset(v1,-1,sizeof v1);
	memset(v2,-1,sizeof v2);
	queue<node> q1,q2;
	q1.push({1,1});
	q2.push({n,m});
	v1[1][1]=0;
	v2[n][m]=0;
	while(q1.size() && q2.size()){//有一边走不到就不行 
		if(q1.size()>q2.size()){//先执行q1 
			node n1=q1.front();
			q1.pop();
			for(int i=0;i<4;i++){
				int xx=n1.x+dx[i];
				int yy=n1.y+dy[i];
				if(xx>=1 && xx<=n && yy>=1 && yy<=m && g[xx][yy]!='#' && v1[xx][yy]==-1){
					q1.push({xx,yy});
					v1[xx][yy]=v1[n1.x][n1.y]+1;
					if(v2[xx][yy]!=-1)return v1[xx][yy]+v2[xx][yy]+1;//相遇 
				}
			} 
		}
		else{
			node n2=q2.front();
			q2.pop();
			for(int i=0;i<4;i++){
				int xx=n2.x+dx[i];
				int yy=n2.y+dy[i];
				if(xx>=1 && xx<=n && yy>=1 && yy<=m && g[xx][yy]!='#' && v2[xx][yy]==-1){
					q2.push({xx,yy});
					v2[xx][yy]=v2[n2.x][n2.y]+1;
					if(v1[xx][yy]!=-1)return v1[xx][yy]+v2[xx][yy]+1;//相遇 
				}
			} 
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
		}
	}
	cout<<bfs();
}