#include<vector>
using namespace std;

struct coordinate{
    int x;
    int y;
    int last;
    int less;
    int more;
    int cost;
    int round;
    coordinate() : x(0), y(0) , last(0), less(0), more(0), cost(0), round(0) {}
    coordinate(int c1, int c2, int c3, int c4, int c5, int c6, int c7) : x(c1), y(c2), last(c3), less(c4), more(c5), cost(c6), round(c7) {}
    
};
typedef struct coordinate coordinate; 
    
coordinate p, end_;
vector<coordinate>list;

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;
    }
}

int solution(vector<vector<int> > maps)
{
    p.x=0;
    p.y=0;
    p.last=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, -1, 1, ch_can});
    list.push_back({0, 0, -1, -1, -1, 1, ch_can});
    
    for(int i=0;i<1000;i++){
        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;
            }
        }
        
        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(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();
        
    }
    
    return maps[end_.y][end_.x];
}