[백준 2178] 미로 탐색

m,n=map(int,input().split())

M=[input() for _ in range(m)]

 

a=[]

b=set()

 

a.append([(m,n)])

b.add((m,n))

k=0

if (1,1)==(m,n):

    print(1)

    

while (1,1)!=(m,n):

    d=set()

    for i in range(len(a[k])):

        if 0<a[k][i][0]-1<=m:

            if M[a[k][i][0]-2][a[k][i][1]-1]=='1' and ((a[k][i][0]-1,a[k][i][1]) in b)==False:

                b.add((a[k][i][0]-1,a[k][i][1]))

                d.add((a[k][i][0]-1,a[k][i][1]))

        if 0<a[k][i][1]-1<=n:

            if M[a[k][i][0]-1][a[k][i][1]-2]=='1' and ((a[k][i][0],a[k][i][1]-1) in b)==False:

                b.add((a[k][i][0],a[k][i][1]-1))

                d.add((a[k][i][0],a[k][i][1]-1))

        if 0<a[k][i][0]+1<=m:

            if M[a[k][i][0]][a[k][i][1]-1]=='1' and ((a[k][i][0]+1,a[k][i][1]) in b)==False:

                b.add((a[k][i][0]+1,a[k][i][1]))

                d.add((a[k][i][0]+1,a[k][i][1]))

        if 0<a[k][i][1]+1<=n:

            if M[a[k][i][0]-1][a[k][i][1]]=='1' and ((a[k][i][0],a[k][i][1]+1) in b)==False:

                b.add((a[k][i][0],a[k][i][1]+1))

                d.add((a[k][i][0],a[k][i][1]+1))

    a.append(list(d))

    k+=1

    if ((1,1) in d)==True :

        print(k+1)

        break