import heapq as hq
from collections import deque
import sys
read = sys.stdin.readline

m, n = map(int, read().split())
maiz = list(list(read().strip()) for _ in range(n))
#해당 좌표까지 도달하는데 부숴야하는 벽의 최소 개수
check = list(list(-1 for _ in range(m)) for _ in range(n))
check[0][0] = 0

#첫 번째 값은 해당 좌표까지 부수면서 온 벽의 개수, 두세번째 값은 좌표를 나타낸다.
point = [[0, 0, 0]]
#벽을 최소로 부순 경우 우선적으로 탐색해나가기 위해 heapq를 사용해 최소값들 우선적으로 추출해 낸다.
hq.heapify(point)

dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]

while point:
    wall, a, b = hq.heappop(point)
    for x, y in zip(dx, dy):
        ax, by = a+x, b+y
        #이미 check에 값이 저장되어 있으면, 그 값이 최소로 부순 벽의 개수임으로 다시 탐색할 필요가 없다.
        if 0 <= ax < n and 0 <= by < m and check[ax][by] == -1:
            if maiz[ax][by] == '1':
                hq.heappush(point, [wall+1, ax, by])
                check[ax][by] = wall+1
            else:
                hq.heappush(point, [wall, ax, by])
                check[ax][by] = wall
print(check[-1][-1])

import sys
read=sys.stdin.readline

a,b,c=map(int,read().split())

b=bin(b)[2:]

answer=1
for i in b[::-1]:
    if i =='1':
        answer=(answer*a)%c
    a=(a*a)%c
print(answer)

import sys
import heapq
from collections import deque
read = sys.stdin.readline
inf = sys.maxsize

v = int(read())
bridge = dict()
for _ in range(v):
    tmp = list(map(int, read().split()))
    bridge[tmp[0]-1] = []
    i = 1
    while True:
        if tmp[i] == -1:
            break
        bridge[tmp[0]-1].append([tmp[i+1], tmp[i]-1])
        i += 2

# x Node로 부터 가장 먼 점의 거리 & 좌표 추출 - 다익스트라 알고리즘 활용


def bfs_far(x):
    # 가장 먼 점의 거리, 좌표 저장
    save = [0, 0]
    # 거리 저장
    check = list(inf for _ in range(v))
    check[x] = 0

    # 최단거리의 아직 방문하지 않은 점들 부터 탐색해나가기 위해 거리정보를 앞에 저장한다.
    hq = [[0, x]]
    heapq.heapify(hq)
    while hq:
        w, n = heapq.heappop(hq)
        # w가 기존에 저장된 거리보다 크다면, save값을 갱신한다.
        if w > save[0]:
            save = [w, n]
        for b in bridge[n]:
            if check[b[1]] == inf:
                check[b[1]] = min(check[b[1]], b[0]+w)
                heapq.heappush(hq, [check[b[1]], b[1]])
            # check의 값이 업데이트 된 점의 경우에는 이미 hq에 추가되어 있기 때문에 다시 추가하지 않는다.
            else:
                check[b[1]] = min(check[b[1]], b[0]+w)

    return save


# 반드시 1부터 탐색해야할 필요는 없다. 어떤 Node 부터 탐색하더라도 결과는 같다.
x = bfs_far(0)
answer=bfs_far(x[1])[0]
print(answer)