双向bfs

``` #include<bits/stdc++.h> using namespace std; int n,m; int a[1000][1000]; int vis[1000][1000][2]; int ps[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}}; queue<pair<int,int> >q[2]; int double_bfs() { q[0].push(make_pair(1,1)); q[1].push(make_pair(n,m)); int x,y; while(1) { x=q[0].front().first; y=q[0].front().second; q[0].pop(); for(int i=1;i<=4;i++) { if(x+ps[i][0]>=1&&x+ps[i][0]<=n&&y+ps[i][1]>=1&&y+ps[i][1]<=m) if(a[x+ps[i][0]][y+ps[i][1]]) if(!vis[x+ps[i][0]][y+ps[i][1]][0]) { vis[x+ps[i][0]][y+ps[i][1]][0]=vis[x][y][0]+1; q[0].push(make_pair(x+ps[i][0],y+ps[i][1])); if(vis[x+ps[i][0]][y+ps[i][1]][1]) { return (vis[x+ps[i][0]][y+ps[i][1]][0]+vis[x+ps[i][0]][y+ps[i][1]][1]); } } } x=q[1].front().first; y=q[1].front().second; q[1].pop(); for(int i=1;i<=4;i++) { if(x+ps[i][0]>=1&&x+ps[i][0]<=n&&y+ps[i][1]>=1&&y+ps[i][1]<=m) if(a[x+ps[i][0]][y+ps[i][1]]) if(!vis[x+ps[i][0]][y+ps[i][1]][1]) { vis[x+ps[i][0]][y+ps[i][1]][1]=vis[x][y][1]+1; q[1].push(make_pair(x+ps[i][0],y+ps[i][1])); if(vis[x+ps[i][0]][y+ps[i][1]][0]) { return (vis[x+ps[i][0]][y+ps[i][1]][0]+vis[x+ps[i][0]][y+ps[i][1]][1]); } } } } return 0; } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { char c; scanf("\n"); for(int j=1;j<=m;j++) { scanf("%c",&c); a[i][j]=c-'0'; } } if(!a[1][1]) { printf("No\n"); } int ans=double_bfs(); if(ans) { printf("%d\n",ans); } else { printf("No\n"); } return 0; } //vis数组既可以表示有没有走过同时表示距离 ```