#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; 
    
coordinate p, end_;
vector<coordinate>list;
int seed;

void update_seed(){
    while(list[seed].round==0){
        seed=list[seed].more;
    }
}

void update_p(){
    p.x=list[seed].x;
    p.y=list[seed].y;
    p.bcost=list[seed].bcost+1;
    p.less=seed;
    update_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){
    for(int i=seed; list[i].more!=-1; i=list[i].more){
        if(n>list[i].bcost+list[i].acost)
            return i-1;
    }
}

int solution(vector<vector<int> > maps)
{
    p.x=0;
    p.y=0;
    p.bcost=1;
    p.less=1;
    end_.x=maps[0].size()-1;
    end_.y=maps.size()-1;
    int ch_round, ch_can = 0;
    
    ch_round=0;
    ch_can = 0;

    //현재 위치 주위 확인
    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({1, 1, -1, -1, 0, end_.x+end_.y+1, 0});
    list.push_back({1, 1, -1, -1, 0, end_.x+end_.y+1, ch_round});
    seed = 1;
    int j;
    
    for(int i=0;i<10000;i++){
        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]){
            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>2){
            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);
                    list.push_back({p.y, p.x, j, list[j].more, p.bcost, newsumcost-p.bcost, ch_round});
                    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);
                list.push_back({p.y, p.x, j, -1, p.bcost, newsumcost-p.bcost, ch_round});
            }
            update_p();
        }
        
        //통로
        if(ch_round<3){
            p.bcost++;
            go_next(ch_can);
            //if(i!=0) return p.y;
            continue;
        }
        
    }
    
    int answer = 0;
    return p.y;
}