#include<vector>
using namespace std;

struct coordinate{
    int x;
    int y;
    int last[4];
    int cost;
    int round;
    coordinate() : x(0), y(0) , last{-1,-1,-1,-1}, cost(0), round(0) {}
    coordinate(int c1, int c2, int c3, int c4, int c5) : x(c1), y(c2), last{c3, -1, -1, -1}, cost(c4), round(c5) {}
    
};
typedef struct coordinate coordinate; 
    
coordinate p, end_;
vector<coordinate>list;
int 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.x++;
        return;
    }
}

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

void update_p(){
    p.cost=1;
    for(int i=seed;i<list.size();i++){
        if(list[i].round){
            p.last[0]=i;
            if(list[i].round | 2){
                p.round = 4;
                p.x=list[i].x+1;
                p.y=list[i].y;
                list[i].round = list[i].round & (31-2);
                update_seed();
                return;
            }
            if(list[i].round | 4){
                p.round = 2;
                p.x=list[i].x-1;
                p.y=list[i].y;
                list[i].round = list[i].round & (31-4);
                update_seed();
                return;
            }
            if(list[i].round | 8){
                p.round = 16;
                p.y=list[i].y-1;
                p.x=list[i].x;
                list[i].round = list[i].round & (31-8);
                update_seed();
                return;
            }
            if(list[i].round | 16){
                p.round = 8;
                p.x=list[i].y+1;
                p.x=list[i].x;
                list[i].round = list[i].round & (31-16);
                update_seed();
                return;
            }
        }
    }
}

int solution(vector<vector<int> > maps)
{
    p.x=0;
    p.y=0;
    p.last[0]=0;
    p.cost=1;
    end_.x=maps[0].size()-1;
    end_.y=maps.size()-1;
    int ch_round, ch_can = 0;
    
    if(p.x+1 <= end_.x && maps[p.y][p.x+1]){
        ch_can=ch_can|2;
    }
    else if(p.x-1 > 0 && maps[p.y][p.x-1]){
        ch_can=ch_can|4;
    }
    else if(p.y-1 > 0 && maps[p.y-1][p.x]){
        ch_can=ch_can|8;
    }
    else if(p.y+1 <= end_.y && maps[p.y+1][p.x]){
        ch_can=ch_can|16;
    }
    
    list.push_back({0, 0, -1, 1, ch_can});
    seed=1;
    
    for(int i=0;i<1000;i++){
        //변수 초기화
        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;
        }
        else if(p.x-1 > 0 && maps[p.y][p.x-1]){
            ch_round++;
            ch_can=ch_can|4;
        }
        else if(p.y-1 > 0 && maps[p.y-1][p.x]){
            ch_round++;
            ch_can=ch_can|8;
        }
        else if(p.y+1 <= end_.y && maps[p.y+1][p.x]){
            ch_round++;
            ch_can=ch_can|16;
        }
        
        //방문 경험이 있는 분기점
        /*if(maps[p.y][p.x] != 1){
            if(p.cost<list[maps[p.y][p.x]].cost){
                list[maps[p.y][p.x]].cost = p.cost;
                list[maps[p.y][p.x]].last = p.last[0];
            }
        }*/
        
        if(ch_round==0) break;// <- 모든 분기점이 확인 되었을 때로 수정해야 함
        
        //통로
        if(ch_round<3){
            maps[p.y][p.x]=0;
            p.cost++;
            go_next(ch_can);
            continue;
        }
        
        //새로운 분기점
        maps[p.y][p.x]=list.size();
        list.push_back({p.x, p.y, p.last[0], p.cost, ch_can});
        update_p();
    }
    
    return maps[end_.y][end_.x];
}