1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=55;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,vis[N][N][N][N]; char g[N][N];
struct node{int x1,y1,x2,y2;};
void bfs(){
    queue<node> q; q.push({1,1,n,m}); memset(vis,-1,sizeof vis); vis[1][1][n][m]=0;
    while(q.size()){
        node u=q.front(); q.pop();
        for(int i=0,tx1,tx2,ty1,ty2;i<4;i++){
            tx1=u.x1+dx[i],ty1=u.y1+dy[i];
            tx2=u.x2-dx[i],ty2=u.y2-dy[i];
            if(tx1<=0||tx1>n||ty1<=0||ty1>m||g[tx1][ty1]=='1') tx1=u.x1,ty1=u.y1;
            if(tx2<=0||tx2>n||ty2<=0||ty2>m||g[tx2][ty2]=='1') tx2=u.x2,ty2=u.y2;
            if(tx1==tx2&&ty1==ty2)  continue;
            if((tx1==u.x2&&ty1==u.y2)&&(tx2==u.x1&&ty2==u.y1))  continue;
            if(vis[tx1][ty1][tx2][ty2]!=-1) continue;
            vis[tx1][ty1][tx2][ty2]=vis[u.x1][u.y1][u.x2][u.y2]+1;
            q.push({tx1,ty1,tx2,ty2});
        }
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)   scanf("%s",g[i]+1);
    if(n==1&&m==1)  return puts("-1"),0;
    bfs();
    cout<<vis[n][m][1][1];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX