#include<vector>
using namespace std;

struct coordinate{
    int x;
    int y;
    int next;
    int last;
    coordinate() : y(0), x(0), next(0), last(0) {}
    coordinate(int c1, int c2, int c3, int c4) : y(c1), x(c2), next(c3), last(c4) {}
};
typedef struct coordinate coordinate;

coordinate p, last, end_;

int solution(vector<vector<int> > maps)
{
    vector<coordinate> list;
    list.push_back({0,0,1,0});
    p.x=0;
    p.y=0;
    p.next=0;
    last.x=0;
    last.y=0;
    last.next=0;
    end_.x=maps[0].size();
    end_.y=maps.size();
    int seed=0;
    int ch;
    
    int asdf=0;
    if(!maps[0][0]) return -1;
    maps[0][0]=0;
    
    for(int i=2; i<10000; i++, seed=list[seed].next){
        ch=list.size();
        for(int j=seed; j<ch; j++){
            if(list[j].y==end_.y-1 && list[j].x==end_.x-1) return i-1;
            //if(list.size()==7) return ch;//maps[list[j].y][list[j].x]*100+list[j].x*10+list[j].y;
            if(list[j].y+1 < end_.y && maps[list[j].y+1][list[j].x]==1){
                list.push_back({list[j].y+1, list[j].x, 0, 0});
                if(!list[seed].next) list[seed].next=(int)list.size()-1;
                maps[list[j].y+1][list[j].x]=i;
            }
            if(list[j].y-1 >= 0 && maps[list[j].y-1][list[j].x]==1){
                list.push_back({list[j].y-1, list[j].x, 0, 0});
                if(!list[seed].next) list[seed].next=(int)list.size()-1;
                maps[list[j].y-1][list[j].x]=i;
            }
            if(list[j].x+1 < end_.x && maps[list[j].y][list[j].x+1]==1){
                list.push_back({list[j].y, list[j].x+1, 0, 0});
                if(!list[seed].next) list[seed].next=(int)list.size()-1;
                maps[list[j].y][list[j].x+1]=i;
            }
            if(list[j].x-1 >= 0 && maps[list[j].y][list[j].x-1]==1){
                list.push_back({list[j].y, list[j].x-1, 0, 0});
                if(!list[seed].next) list[seed].next=(int)list.size()-1;
                maps[list[j].y][list[j].x-1]=i;
            }
            //if(j==5) return list.size();//maps[list[j].y][list[j].x]*100+list[j].x*10+list[j].y;
        }
        if(ch==list.size()) return -1;
    }
    
    return -1;
    int a = 8;
    //return list[a].next;
    //return maps[list[a].y][list[a].x]*100+list[a].x*10+list[a].y;
}