#include<vector>
using namespace std;

struct coordinate{
    int x;
    int y;
    int less;
    int more;
    int bcost;
    int acost;
    int round;
    coordinate() : x(0), y(0), less(0), more(0), bcost(0), acost(0), round(0) {}
    coordinate(int c1, int c2, int c3, int c4, int c5, int c6, int c7) : x(c1), y(c2), less(c3), more(c4), bcost(c5), acost(c6), round(c7) {}
};
typedef struct coordinate coordinate; 
    

int asdf;


coordinate p, end_;
vector<coordinate>list;
int seed;

void update_seed(){
    int newround=(list[seed].round==0 ? 0:(list[seed].round & 2)/2 + (list[seed].round & 4)/4 + (list[seed].round & 8)/8 + (list[seed].round & 16)/16);
    while(newround<1){
        seed=list[seed].more;
        newround=(list[seed].round==0 ? 0:(list[seed].round & 2)/2 + (list[seed].round & 4)/4 + (list[seed].round & 8)/8 + (list[seed].round & 16)/16);
    }
}

void update_p(){
    update_seed();
    p.x=list[seed].x;
    p.y=list[seed].y;
    p.bcost=list[seed].bcost+1;
    p.less=seed;
}

void go_next(int n){
    if(n & 2 && !(p.round & 2)){
        p.round = 4;
        p.x++;
        return;
    }
    if(n & 4 && !(p.round & 4)){
        p.round = 2;
        p.x--;
        return;
    }
    if(n & 8 && !(p.round & 8)){
        p.round = 16;
        p.y--;
        return;
    }
    if(n & 16 && !(p.round & 16)){
        p.round = 8;
        p.y++;
        return;
    }
}

int new_list_point(int n){
    int i;
    int newround;
    for(i=seed; list[i].more!=-1; i=list[i].more){
        newround=(list[i].round==0 ? 0:(list[i].round & 2)/2 + (list[i].round & 4)/4 + (list[i].round & 8)/8 + (list[i].round & 16)/16);
        if(newround<1){
            //newround=list[i].more;
            if(list[i].more!=-1 && list[list[i].more].less == i) list[list[i].more].less=list[i].less;
            if(list[i].less!=-1 && list[list[i].less].more == i) list[list[i].less].more=list[i].more;
        }
        else if(n<=list[i].bcost+list[i].acost)
            return i-1;
    }
    return i;
}

int solution(vector<vector<int> > maps)
{
    asdf=0;
    p.x=0;
    p.y=0;
    p.bcost=0;
    p.less=1;
    end_.x=maps[0].size()-1;
    end_.y=maps.size()-1;
    int ch_round=0, ch_can = 0;
    if(maps[0][0] == 0 || maps[end_.y][end_.x] == 0) return -1;
    
    int n_map[100][100]={0};
    
    for(int i=0;i<=end_.x; i++){
        n_map[0][i]=!maps[0][i];
    }
    for(int i=0;i<=end_.y; i++){
        n_map[i][end_.x]=!maps[i][end_.x];
    }
    
    while(p.less<=end_.y && end_.x>=0){
        for(p.x=0; p.x<=end_.x;p.x++){
            if(n_map[p.y][p.x]!=0){
                for(int i=-1;i<2;i++){
                    if(p.x+i>=0 && p.x+i<end_.x){
                        n_map[p.y+1][p.x+i] += !maps[p.y+1][p.x+i];
                    }
                }
            }
        }
        p.x=end_.x--;
        for(;p.y<=end_.y;p.y++){
            if(n_map[p.y][p.x]!=0){
                for(int i=-1;i<2;i++){
                    if(p.y+i>=p.less && p.y+i<=end_.y){
                        n_map[p.y+i][p.x-1] += !maps[p.y+i][p.x-1];
                    }
                }
            }
        }
        p.y=p.less++;
    }
    
    p.x=0;
    p.y=0;
    p.less=1;
    end_.x=maps[0].size()-1;
    end_.y=maps.size()-1;
    ch_round=0;
    ch_can = 0;
    
    //return n_map[4][3];
    
    for(int i=0;i<=end_.x; i++){
        if(n_map[end_.y][i]>0) return -1;
    }
    for(int i=0;i<=end_.y; i++){
        if(n_map[i][0]>0) return -1;
    }

    //현재 위치 주위 확인
    if(p.x+1 <= end_.x && maps[p.y][p.x+1]){
        ch_round++;
        ch_can=ch_can|2;
    }
    if(p.x-1 >= 0 && maps[p.y][p.x-1]){
        ch_round++;
        ch_can=ch_can|4;
    }
    if(p.y-1 >= 0 && maps[p.y-1][p.x]){
        ch_round++;
        ch_can=ch_can|8;
    }
    if(p.y+1 <= end_.y && maps[p.y+1][p.x]){
        ch_round++;
        ch_can=ch_can|16;
    }
    
    if(ch_round==0) return -1;
    list.push_back({0, 0, -1, -1, 0, end_.x+end_.y+1, 0});
    list.push_back({0, 0, -1, -1, 0, end_.x+end_.y+1, ch_can});
    seed = 1;
    
    if(p.x<p.y && p.y+1 <= end_.y && maps[p.y+1][p.x]){
        p.round = 8;
        p.y++;
        list[1].round=list[1].round & (31-16);
    }
    else if(p.x+1 <= end_.x && maps[p.y][p.x+1]){
        p.round = 4;
        p.x++;
        list[1].round=list[1].round & (31-2);
    }
    else if(p.y+1 <= end_.y && maps[p.y+1][p.x]){
        p.round = 8;
        p.y++;
        list[1].round=list[1].round & (31-16);
    }
    p.bcost++;

    int i, j;
    
    //for(i=0;i<15;i++){//120000
    while(1){
        if(end_.x+end_.y-p.x-p.y == 0) break;
        ch_round=0;
        ch_can = 0;
        
        //현재 위치 주위 확인
        if(p.x+1 <= end_.x && maps[p.y][p.x+1] && !(p.round & 2)){
            ch_round++;
            ch_can=ch_can|2;
        }
        if(p.x-1 >= 0 && maps[p.y][p.x-1] && !(p.round & 4)){
            ch_round++;
            ch_can=ch_can|4;
        }
        if(p.y-1 >= 0 && maps[p.y-1][p.x] && !(p.round & 8)){
            ch_round++;
            ch_can=ch_can|8;
        }
        if(p.y+1 <= end_.y && maps[p.y+1][p.x] && !(p.round & 16)){
            ch_round++;
            ch_can=ch_can|16;
        }
        
        //if(p.x==end_.x && p.y==end_.y)    return 1234;//p.bcost+1;
        
        //분기점
        if(ch_round!=1){
            int newsumcost=p.bcost+end_.x+end_.y-p.x-p.y+1;
            /*for(j=seed;list[j].more!=-1;j=list[j].more){
                if(list[j].bcost+list[j].acost<newsumcost){
                    j = new_list_point(newsumcost);
                    if(list[list[j].more].less != -1){
                        list[list[j].more].less=list.size();
                    }
                    list[j].more=list.size();
                    list.push_back({p.y, p.x, j, list[j].more, p.bcost, newsumcost-p.bcost, ch_round});
                    if(list[list.size()-1].more != -1)list[list[list.size()-1].more].less=list.size()-1;
                    list[list[list.size()-1].less].more=list.size()-1;
                    break;
                }
            }
            if(j!=-1 && list[j].more==-1){
                j = new_list_point(newsumcost);
                if(list[list[j].more].less != -1){
                    list[list[j].more].less=list.size();
                }
                list[j].more=list.size();
                list.push_back({p.y, p.x, j, -1, p.bcost, newsumcost-p.bcost, ch_round});
            }*/

            
            j = new_list_point(newsumcost);
            
            if(list[j].more == -1){
                list.push_back({p.x, p.y, j, -1, p.bcost, newsumcost-p.bcost, ch_can});
                list[j].more=list.size()-1;
            }
            else{
                list.push_back({p.x, p.y, j, list[j].more, p.bcost, newsumcost-p.bcost, ch_can});
                list[list[j].more].less=list.size()-1;
                list[j].more=list.size()-1;
            }
            
            /*if(i==10){
                update_p();
                return seed;//p.x*10+p.y;
            }*/
            
            if(list[j].bcost+list[j].acost >= newsumcost){
                p.bcost++;
                p.less=list.size()-1;
                //return -1;
            }
            else{
                update_p();
                //if(i==13) return seed;
            }
            
            if(p.x>=p.y && p.y+1 <= end_.y && maps[p.y+1][p.x] && list[p.less].round & 16){
                p.round = 8;
                list[p.less].round=list[p.less].round & (31-16);
                p.y++;
            }
            else if(p.x+1 <= end_.x && maps[p.y][p.x+1] && list[p.less].round & 2){
                p.round = 4;
                list[p.less].round=list[p.less].round & (31-2);
                p.x++;
            }
            else if(p.y+1 <= end_.y && maps[p.y+1][p.x] && list[p.less].round & 16){
                p.round = 8;
                list[p.less].round=list[p.less].round & (31-16);
                p.y++;
            }
            else if(p.y-1 >= 0 && maps[p.y-1][p.x] && list[p.less].round & 4){
                p.round = 2;
                list[p.less].round=list[p.less].round & (31-4);
                p.x--;
            }
            else if(p.x-1 >= 0 && maps[p.y][p.x-1] && list[p.less].round & 8){
                p.round = 16;
                list[p.less].round=list[p.less].round & (31-8);
                p.y--;
            }
        }
        
        //if(i==12) return list.size();
        
        //통로
        if(ch_round==1){
            p.bcost++;
            go_next(ch_can);
            //if(i!=0) return p.y;
            continue;
        }
        
    }
    
    //return asdf;
    //return p.bcost*100+p.x*10+p.y;
    //return i;
    int answer = 0;
    //if(i==60000000) return -1;
    return p.bcost+1;
}