#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<2){
        seed=list[seed].more;
    }
}

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;
    for(i=seed; list[i].more!=-1; i=list[i].more){
        if(n>list[i].bcost+list[i].acost && list[i].round>1)
            return i-1;
    }
    return i;
}

int solution(vector<vector<int> > maps)
{
    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, 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;
    
    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 j;
    
    for(int i=0;i<6;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] && !(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});
                    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});
            }
            update_p();
            if(p.x<p.y && p.y+1 <= end_.y && maps[p.y+1][p.x]){
                p.round = 8;
                list[list.size()-1].round=list[list.size()-1].round & (31-16);
                p.y++;
            }
            else if(p.x+1 <= end_.x && maps[p.y][p.x+1]){
                p.round = 4;
                list[list.size()-1].round=list[list.size()-1].round & (31-2);
                p.x++;
            }
            else if(p.y+1 <= end_.y && maps[p.y+1][p.x]){
                p.round = 8;
                list[list.size()-1].round=list[list.size()-1].round & (31-16);
                p.y++;
            }
            else if(p.y-1 >= 0 && maps[p.y-1][p.x]){
                p.round = 2;
                list[list.size()-1].round=list[list.size()-1].round & (31-4);
                p.x--;
            }
            else if(p.x-1 >= 0 && maps[p.y][p.x-1]){
                p.round = 16;
                list[list.size()-1].round=list[list.size()-1].round & (31-8);
                p.y--;
            }
        }
        
        //통로
        if(ch_round<2){
            p.bcost++;
            go_next(ch_can);
            //if(i!=0) return p.y;
            continue;
        }
        
    }
    
    int answer = 0;
    if(p.bcost==1001) return -1;
    return list.size();
}