turns.py

from collections import defaultdict
import heapq

m, n = map(int, raw_input().split())
grid = [map(int, raw_input().split()) for _ in xrange(m)]

d = defaultdict(lambda: defaultdict(lambda: float('inf')))
for row in xrange(m):
    for i in xrange(n):
        for j in xrange(i + 1, n):
            if all(grid[row][i : j + 1]):
                d[row, i][row, j] = 1
                d[row, j][row, i] = 1

for col in xrange(n):
    for i in xrange(m):
        for j in xrange(i + 1, m):
            if all(grid[k][col] for k in xrange(i, j + 1)):
                d[i, col][j, col] = 1
                d[j, col][i, col] = 1

visited = set()
deleted = set()
heap = [(0, (0, 0))]
dd = defaultdict(lambda: float('inf'))

while True:
    while heap and heap[0] in deleted:
        deleted.remove(heapq.heappop(heap))

    da, a = heapq.heappop(heap)
    if a == (m - 1, n - 1):
        break
    visited.add(a)
    for ng in d[a]:
        if ng in visited:
            continue
        if da + d[a][ng] < dd[ng]:
            deleted.add((dd[ng], ng))
            dd[ng] = da + d[a][ng]
            heapq.heappush(heap, (dd[ng], ng))

print dd[m - 1, n - 1] - 1