Given a 2D binary matrix A(0-based index) of dimensions NxM. Find the minimum number of steps required to reach from (0,0) to (X, Y).
Note: You can only move left, right, up and down, and only through cells that contain 1.
Example 1:
Input:
N=3
M=4
A=[[1,0,0,0], 
[1,1,0,1],[0,1,1,1]]
X=2
Y=3 
Output:
5
Explanation:
The shortest path is as follows:
(0,0)->(1,0)->(1,1)->(2,1)->(2,2)->(2,3).
Example 2:
Input:
N=3
M=4
A=[[1,1,1,1],
[0,0,0,1],[0,0,0,1]]
X=0
Y=3
Output:
3
Explanation:
The shortest path is as follows:
(0,0)->(0,1)->(0,2)->(0,3).
Your Task:
You don't need to read input or print anything. Your task is to complete the function shortestDistance() which takes the integer N, M, X, Y, and the 2D binary matrix A as input parameters and returns the minimum number of steps required to go from (0,0) to (X, Y).If it is impossible to go from (0,0) to (X, Y),then function returns -1. If value of the cell (0,0) is 0 (i.e  A[0][0]=0) then return -1.
Expected Time Complexity:O(N*M)
Expected Auxillary Space:O(N*M)
 
Constraints:
1 <= N,M <= 250
0 <= X < N
0 <= Y < M
0 <= A[i][j] <= 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3

class Solution:
    def shortestDistance(self,N,M,A,X,Y):
        #code here

Solutions:
from queue import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		direction = [[0, 1], [-1, 0], [1, 0], [0, -1]]
		q = deque()
		q.append((0, 0, 0))
		visited = set()
		visited.add((0, 0))
		while q:
			(row, col, steps) = q.popleft()
			if row == X and col == Y:
				return steps
			for dir in direction:
				n_r = row + dir[0]
				n_c = col + dir[1]
				if n_r >= 0 and n_c >= 0 and (n_r < len(A)) and (n_c < len(A[0])) and (A[n_r][n_c] == 1) and ((n_r, n_c) not in visited):
					q.append((n_r, n_c, steps + 1))
					visited.add((n_r, n_c))
		return -1


from queue import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
		q = deque()
		v = set()
		v.add((0, 0))
		q.append((0, 0, 0))
		while q:
			(row, col, steps) = q.popleft()
			if row == X and col == Y:
				return steps
			for dir in directions:
				newRow = row + dir[0]
				newCol = col + dir[1]
				if newRow >= 0 and newRow < len(A) and (newCol >= 0) and (newCol < len(A[0])):
					if A[newRow][newCol] == 1 and (newRow, newCol) not in v:
						q.append((newRow, newCol, steps + 1))
						v.add((newRow, newCol))
		return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		(sr, sc) = (0, 0)
		if A[sr][sc] == 0:
			return -1
		(rq, cq) = ([], [])
		visited = [[False for i in range(M)] for j in range(N)]
		visited[sr][sc] = True
		rq.append(sr)
		cq.append(sc)
		dr = [-1, 1, 0, 0]
		dc = [0, 0, 1, -1]
		reached_end = False
		nodes_in_next_layer = 0
		nodes_left_in_layer = 1
		move_count = 0
		while len(rq) > 0:
			r = rq.pop(0)
			c = cq.pop(0)
			if r == X and c == Y:
				return move_count
			for i in range(4):
				rr = r + dr[i]
				cc = c + dc[i]
				if rr < 0 or cc < 0:
					continue
				if rr >= N or cc >= M:
					continue
				if A[rr][cc] == 0:
					continue
				if visited[rr][cc]:
					continue
				rq.append(rr)
				cq.append(cc)
				visited[rr][cc] = True
				nodes_in_next_layer += 1
			nodes_left_in_layer -= 1
			if nodes_left_in_layer == 0:
				nodes_left_in_layer = nodes_in_next_layer
				nodes_in_next_layer = 0
				move_count += 1
		return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		ans = -1
		queue = [(0, 0, 0)]
		while len(queue) > 0:
			(i, j, level) = queue.pop(0)
			if (i, j) == (X, Y):
				ans = level
				break
			for dx in (-1, 1):
				u = i + dx
				v = j
				if 0 <= u < N and A[u][v] == 1:
					queue.append((u, v, level + 1))
					A[u][v] = 0
			for dy in (-1, 1):
				u = i
				v = j + dy
				if 0 <= v < M and A[u][v] == 1:
					queue.append((u, v, level + 1))
					A[u][v] = 0
		return ans


import heapq

class Solution:

	def shortestDistance(self, n, m, a, x, y):
		hp = []
		if a[0][0] == 1:
			heapq.heappush(hp, [0, 0, 0])
		else:
			return -1
		a[0][0] = 0
		dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		while hp:
			(dist, i, j) = heapq.heappop(hp)
			if i == x and y == j:
				return dist
			for (d1, d2) in dir:
				new_x = d1 + i
				new_y = d2 + j
				if new_x < 0 or new_x >= n or new_y < 0 or (new_y >= m) or (a[new_x][new_y] == 0):
					continue
				heapq.heappush(hp, [dist + 1, new_x, new_y])
				a[new_x][new_y] = 0
		return -1


class Solution:

	def shortestDistance(self, n, m, A, X, Y):

		def neighbors(A, i, j, n, m):
			di = [-1, 0, 1, 0]
			dj = [0, 1, 0, -1]
			l = []
			for k in range(4):
				p = i + di[k]
				q = j + dj[k]
				if p >= 0 and p < n and (q >= 0) and (q < m) and (A[p][q] == 1):
					l.append([p, q])
			return l
		if A[0][0] == 0:
			return -1
		q = []
		q.append([0, 0])
		A[0][0] = 0
		cnt = 0
		while len(q) > 0:
			sz = len(q)
			for z in range(sz):
				pt = q.pop(0)
				i = pt[0]
				j = pt[1]
				if i == X and j == Y:
					return cnt
				nei = neighbors(A, i, j, n, m)
				for ne in nei:
					q.append(ne)
					A[ne[0]][ne[1]] = 0
			cnt += 1
		return -1


class QueueNode:

	def __init__(self, x, y, d=0):
		self.x = x
		self.y = y
		self.d = d

def isValid(i, j, N, M):
	return i >= 0 and i < N and (j >= 0) and (j < M)

class Solution:

	def shortestDistance(self, N, M, nums, X, Y):
		if nums[0][0] != 1:
			return -1
		visited = [[False for _ in range(M)] for _ in range(N)]
		start = QueueNode(0, 0)
		visited[0][0] = True
		q = [start]
		diri = [0, -1, 0, 1]
		dirj = [-1, 0, 1, 0]
		while len(q) != 0:
			curr = q.pop(0)
			(x, y, d) = (curr.x, curr.y, curr.d)
			if x == X and y == Y:
				return d
			for k in range(4):
				nexti = x + diri[k]
				nextj = y + dirj[k]
				if isValid(nexti, nextj, N, M) and (not visited[nexti][nextj]) and (nums[nexti][nextj] == 1):
					q.append(QueueNode(nexti, nextj, d + 1))
					visited[nexti][nextj] = True
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		dx = [0, 0, -1, +1]
		dy = [-1, +1, 0, 0]
		dp = [[-1 for _ in range(M)] for _ in range(N)]
		dp[0][0] = 0
		q = deque()
		q.append((0, 0))
		while q:
			(x, y) = q.popleft()
			if dp[X][Y] > -1:
				break
			for k in range(4):
				(newx, newy) = (x + dx[k], y + dy[k])
				if not (0 <= newx < N and 0 <= newy < M) or dp[newx][newy] > -1 or A[newx][newy] == 0:
					continue
				dp[newx][newy] = dp[x][y] + 1
				q.append((newx, newy))
		return dp[X][Y]


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		q = [(0, 0, 0)]
		visited = set()
		visited.add((0, 0))
		while q:
			(i, j, steps) = q.pop(0)
			if i == X and j == Y:
				return steps
			for (ni, nj) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= ni < N and 0 <= nj < M and (A[ni][nj] == 1) and ((ni, nj) not in visited):
					q.append((ni, nj, steps + 1))
					visited.add((ni, nj))
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, n, m, a, x, y):
		if a[0][0] == 0:
			return -1
		dis = [[float('inf')] * m for _ in range(n)]
		q = deque()
		q.append((0, 0, 0))
		dis[0][0] = 0
		while q:
			(d, r, c) = q.popleft()
			l = [[-1, 0], [1, 0], [0, -1], [0, 1]]
			for (i, j) in l:
				(nr, nc) = (r + i, c + j)
				if nr < n and nr >= 0 and (nc < m) and (nc >= 0) and (a[nr][nc] == 1) and (d + 1 < dis[nr][nc]):
					dis[nr][nc] = d + 1
					if (nr, nc) == (x, y):
						return dis[nr][nc]
					q.append((d + 1, nr, nc))
		return -1


class Solution:

	def createAdj(self, N, M, A):
		adj = {}
		for i in range(N):
			for j in range(M):
				if A[i][j] == 1:
					adj[i, j] = []
					if j + 1 < M and A[i][j + 1] == 1:
						adj[i, j].append((i, j + 1))
					if j - 1 >= 0 and A[i][j - 1] == 1:
						adj[i, j].append((i, j - 1))
					if i + 1 < N and A[i + 1][j] == 1:
						adj[i, j].append((i + 1, j))
					if i - 1 >= 0 and A[i - 1][j] == 1:
						adj[i, j].append((i - 1, j))
		return adj

	def bfs(self, N, M, graph, X, Y):
		currentNode = (0, 0)
		queue = []
		queue.append(currentNode)
		visited = []
		visited.append(currentNode)
		parent = {}
		parent[currentNode] = None
		while queue:
			u = queue.pop(0)
			if u[0] == X and u[1] == Y:
				return parent
			for neighbor in graph[u]:
				if neighbor not in visited:
					visited.append(neighbor)
					queue.append(neighbor)
					parent[neighbor] = u
		return {}

	def shortestDistance(self, N, M, A, X, Y):
		graph = self.createAdj(N, M, A)
		if (0, 0) not in graph:
			return -1
		parents = self.bfs(N, M, graph, X, Y)
		if (X, Y) not in parents:
			return -1
		node = (X, Y)
		pathSize = 0
		while node:
			pathSize += 1
			node = parents[node]
		return pathSize - 1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		(self.N, self.M, self.X, self.Y, self.A) = (N, M, X, Y, A)
		count = self.bfs(0, 0)
		if count == 0:
			return -1
		return count

	def bfs(self, i, j):
		if self.A[i][j] == 0:
			return 0
		vector = [(-1, 0), (0, -1), (1, 0), (0, 1)]
		queue = list()
		queue.append((i, j, 0))
		count = 0
		while queue:
			(x, y, z) = queue.pop(0)
			if x == self.X and y == self.Y:
				if self.A[x][y] == 1:
					return z
				return 0
			if self.A[x][y] == 0:
				continue
			self.A[x][y] = 0
			for dir in vector:
				dir1 = x + dir[0]
				dir2 = y + dir[1]
				if 0 <= dir1 < self.N and 0 <= dir2 < self.M:
					queue.append((dir1, dir2, z + 1))
		return count


from queue import PriorityQueue
from collections import deque

class Solution:

	def check(self, cord, r, c, grid):
		if 0 <= cord[0] < r and 0 <= cord[1] < c:
			if grid[cord[0]][cord[1]] == 1:
				return True
		else:
			return False

	def explore(self, grid, dir_x, dir_y, vis, pos, dest):
		(r, c) = (len(grid), len(grid[0]))
		q = PriorityQueue()
		q.put((vis[pos[0]][pos[1]], pos[0], pos[1]))
		while not q.empty():
			a = q.get()
			if a == dest:
				return vis
			for i in range(4):
				(new_x, new_y) = (a[1] + dir_x[i], a[2] + dir_y[i])
				if self.check([new_x, new_y], len(grid), len(grid[0]), grid):
					if vis[new_x][new_y] == 0:
						vis[new_x][new_y] = vis[a[1]][a[2]] + 1
						q.put((vis[new_x][new_y], new_x, new_y))
					elif vis[new_x][new_y] > vis[a[1]][a[2]] + 1:
						vis[new_x][new_y] = vis[a[1]][a[2]] + 1
						q.put((vis[new_x][new_y], new_x, new_y))
		return vis

	def shortestDistance(self, N, M, A, X, Y):
		(row, col) = (len(A), len(A[0]))
		(dis_x, dis_y) = ([0, 0, -1, 1], [-1, 1, 0, 0])
		vis = [[0 for i in range(col)] for j in range(row)]
		if A[0][0] != 1 or A[X][y] != 1:
			return -1
		(dest, src) = ([X, Y], [0, 0])
		a = self.explore(A, dis_x, dis_y, vis, src, dest)
		if a[X][y] > 0:
			return a[X][Y]
		else:
			return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0 or A[X][Y] == 0:
			return -1
		dist = [[float('inf') for i in range(len(A[0]))] for i in range(len(A))]
		visited = [[False for i in range(len(A[0]))] for i in range(len(A))]
		dist[0][0] = 0
		q = [[0, 0]]
		while q:
			cur = q.pop(0)
			(x, y) = cur
			visited[x][y] = True
			for (i, j) in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
				if 0 <= i < len(A) and 0 <= j < len(A[0]) and (A[i][j] == 1) and (visited[i][j] == False):
					visited[i][j] = True
					dist[i][j] = dist[x][y] + 1
					q.append([i, j])
		if dist[X][Y] == float('inf'):
			return -1
		return dist[X][Y]


from sys import maxsize
from collections import deque
import heapq

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		dist = [[maxsize] * M for _ in range(N)]
		dist[0][0] = 0
		q = [(0, 0, 0)]
		while q:
			(i, j, w) = heapq.heappop(q)
			for (dx, dy) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if not (0 <= dx < N and 0 <= dy < M) or A[dx][dy] == 0:
					continue
				if w + 1 < dist[dx][dy]:
					dist[dx][dy] = w + 1
					heapq.heappush(q, (dx, dy, w + 1))
		ans = dist[X][Y]
		return -1 if ans == maxsize else ans


import heapq

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		distance = [[99999 for i in range(M)] for j in range(N)]
		heap = []
		directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		if A[0][0] == 0:
			return -1
		heapq.heappush(heap, [1, 0, 0])
		distance[0][0] = 1
		while heap:
			(wei, i, j) = heapq.heappop(heap)
			for k in directions:
				ii = k[0] + i
				jj = k[1] + j
				if 0 <= ii < len(A) and 0 <= jj < len(A[0]) and (A[ii][jj] == 1):
					if distance[ii][jj] > wei + A[i][j]:
						distance[ii][jj] = wei + A[i][j]
						heapq.heappush(heap, [distance[ii][jj], ii, jj])
		if distance[X][Y] == 99999:
			return -1
		else:
			return distance[X][Y] - 1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0 or A[X][Y] == 0:
			return -1
		queue = deque([(0, 0)])
		visited = [[False] * M for _ in range(N)]
		visited[0][0] = True
		distance = [[float('inf')] * M for _ in range(N)]
		distance[0][0] = 0
		while queue:
			(i, j) = queue.popleft()
			if i == X and j == Y:
				return distance[i][j]
			for (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				ni = i + di
				nj = j + dj
				if ni >= 0 and ni < N and (nj >= 0) and (nj < M) and (A[ni][nj] == 1) and (not visited[ni][nj]):
					visited[ni][nj] = True
					distance[ni][nj] = distance[i][j] + 1
					queue.append((ni, nj))
		return -1
Solution()


class Solution:

	def shortestDistance(self, N, M, grid, X, Y):
		q = [(0, 0)]
		ans = 0
		while q:
			nq = []
			for (x0, y0) in q:
				if x0 < 0 or x0 >= len(grid) or y0 < 0 or (y0 >= len(grid[0])) or (grid[x0][y0] == 0):
					continue
				if x0 == X and y0 == Y:
					return ans
				grid[x0][y0] = 0
				nq.append((x0 + 1, y0))
				nq.append((x0 - 1, y0))
				nq.append((x0, y0 + 1))
				nq.append((x0, y0 - 1))
			q = nq
			ans += 1
		return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		visited = [[False for i in range(M)] for j in range(N)]
		ady = [(0, -1), (0, 1), (1, 0), (-1, 0)]

		def isValid(x, y):
			return 0 <= x and x < N and (y >= 0) and (y < M)
		(q, step) = ([], 0)
		q.append([0, 0, step])
		while q:
			(i, j, s) = q.pop(0)
			if i == X and j == Y:
				return s
			for n in ady:
				(nx, ny) = (i + n[0], j + n[1])
				if isValid(nx, ny) and (not visited[nx][ny]) and (A[nx][ny] == 1):
					q.append([nx, ny, s + 1])
					visited[nx][ny] = True
		return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		dist = [[float('inf') for i in range(M)] for j in range(N)]
		q = []
		q.append([0, 0, 0])
		dist[0][0] = 0
		delr = [-1, 0, 1, 0]
		delc = [0, 1, 0, -1]
		if A[0][0] == 0 or A[X][Y] == 0:
			return -1
		while q:
			it = q.pop(0)
			dis = it[0]
			r = it[1]
			c = it[2]
			if r == X and c == Y:
				return dis
			for i in range(4):
				nrow = r + delr[i]
				ncol = c + delc[i]
				if nrow >= 0 and nrow < N and (ncol >= 0) and (ncol < M) and (A[nrow][ncol] == 1) and (dist[nrow][ncol] > dis + 1):
					dist[nrow][ncol] = dis + 1
					q.append([dis + 1, nrow, ncol])
				if nrow == X and ncol == Y:
					return dis + 1
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		memo = [[-1 for i in range(M)] for j in range(N)]
		q = deque()
		q.append((0, 0, 0))

		def get_n(x, y):
			row = [1, 0, -1, 0]
			col = [0, 1, 0, -1]
			n_s = []
			for i in range(len(row)):
				new_row = x + row[i]
				new_col = y + col[i]
				if 0 <= new_row < N and 0 <= new_col < M:
					n_s.append((new_row, new_col))
			return n_s
		while q:
			(x, y, cnt) = q.popleft()
			memo[x][y] = cnt
			if A[x][y] == 1:
				A[x][y] = 0
				if x == X and y == Y:
					return cnt
				for ne in get_n(x, y):
					(n_x, n_y) = (ne[0], ne[1])
					if memo[n_x][n_y] == -1 and A[n_x][n_y] == 1:
						q.append((n_x, n_y, cnt + 1))
		return -1


import heapq

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		dist = [[float('inf') for _ in range(M)] for _ in range(N)]
		dist[0][0] = 0
		pq = []
		heapq.heappush(pq, (0, (0, 0)))
		while pq:
			(d, u) = heapq.heappop(pq)
			(x, y) = (u[0], u[1])
			dx = [-1, 0, 1, 0]
			dy = [0, 1, 0, -1]
			for i in range(4):
				newr = x + dx[i]
				newc = y + dy[i]
				if newr >= 0 and newr < N and (newc >= 0) and (newc < M) and (A[newr][newc] == 1) and (d + 1 < dist[newr][newc]):
					dist[newr][newc] = d + 1
					if newr == X and newc == Y:
						return dist[newr][newc]
					heapq.heappush(pq, (d + 1, (newr, newc)))
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		q = deque()
		q.append([0, 0, 0])
		vis = []
		for _ in range(N):
			vis.append([False] * M)
		if A[0][0] == 0:
			return -1
		s = 0
		while len(q) > 0:
			(i, j, s) = q.popleft()
			if i == X and j == Y:
				return s
			for dx in (-1, 1):
				u = i + dx
				v = j
				if 0 <= u < N and A[u][v] == 1 and (not vis[u][v]):
					vis[u][v] = True
					q.append([u, v, s + 1])
			for dy in (-1, 1):
				u = i
				v = j + dy
				if 0 <= v < M and A[u][v] == 1 and (not vis[u][v]):
					q.append([u, v, s + 1])
					vis[u][v] = True
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, grid, X, Y):
		if grid[0][0] == 0:
			return -1
		if grid[X][Y] == 0:
			return -1
		q = deque()
		q.append([0, 0])
		lvl = 0
		dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
		visit = set()
		while q:
			n = len(q)
			for i in range(n):
				v = q.popleft()
				for (p, r) in dirs:
					x = v[0] + p
					y = v[1] + r
					if x > len(grid) - 1 or y > len(grid[0]) - 1 or x < 0 or (y < 0):
						continue
					if x == X and y == Y:
						return lvl + 1
					if grid[x][y] != 0 and (x, y) not in visit:
						q.append([x, y])
						visit.add(tuple((x, y)))
			lvl += 1
		return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] != 1 or A[X][Y] != 1:
			return -1
		queue = [(0, 0)]
		steps = 0
		visited = [[-1 for _ in range(M)] for _ in range(N)]
		visited[0][0] = 1
		while queue:
			l = len(queue)
			for i in range(l):
				x = queue.pop(0)
				if x[0] == X and x[1] == Y:
					return steps
				if x[0] + 1 < N and A[x[0] + 1][x[1]] == 1 and (visited[x[0] + 1][x[1]] == -1):
					queue.append((x[0] + 1, x[1]))
					visited[x[0] + 1][x[1]] = 1
				if x[0] - 1 >= 0 and A[x[0] - 1][x[1]] == 1 and (visited[x[0] - 1][x[1]] == -1):
					queue.append((x[0] - 1, x[1]))
					visited[x[0] - 1][x[1]] = 1
				if x[1] + 1 < M and A[x[0]][x[1] + 1] == 1 and (visited[x[0]][x[1] + 1] == -1):
					queue.append((x[0], x[1] + 1))
					visited[x[0]][x[1] + 1] = 1
				if x[1] - 1 >= 0 and A[x[0]][x[1] - 1] == 1 and (visited[x[0]][x[1] - 1] == -1):
					queue.append((x[0], x[1] - 1))
					visited[x[0]][x[1] - 1] = 1
			steps += 1
		return -1


from collections import deque

def isValid(i, j, m, n):
	if i < 0 or j < 0 or i >= m or (j >= n):
		return False
	return True

class Solution:

	def shortestDistance(self, m, n, matrix, x, y):
		if matrix[0][0] != 1 or matrix[x][y] != 1:
			return -1
		q = deque([])
		distance = 0
		q.append([0, 0, 0])
		vis = [[0 for j in range(n)] for i in range(m)]
		while q:
			(i, j, dist) = q.popleft()
			vis[i][j] = 1
			if i == x and j == y:
				return dist
			for k in ([-1, 0], [0, -1], [1, 0], [0, 1]):
				a = i + k[0]
				b = j + k[1]
				if isValid(a, b, m, n) and vis[a][b] == 0 and (matrix[a][b] == 1):
					vis[a][b] = 1
					q.append([a, b, dist + 1])
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		d = [[1000000000.0 for j in range(M)] for i in range(N)]
		c = [['w' for j in range(M)] for i in range(N)]
		d[0][0] = 0
		c[0][0] = 'g'
		if A[0][0] == 0 or X < 0 or X >= N or (Y < 0) or (Y >= M) or (A[X][Y] == 0):
			return -1
		q = deque()
		q.append((0, 0))
		while len(q) > 0:
			(i, j) = q.popleft()
			if i - 1 >= 0 and c[i - 1][j] == 'w' and (A[i - 1][j] == 1):
				c[i - 1][j] = 'g'
				d[i - 1][j] = 1 + d[i][j]
				q.append((i - 1, j))
			if i + 1 < N and c[i + 1][j] == 'w' and (A[i + 1][j] == 1):
				c[i + 1][j] = 'g'
				d[i + 1][j] = 1 + d[i][j]
				q.append((i + 1, j))
			if j - 1 >= 0 and c[i][j - 1] == 'w' and (A[i][j - 1] == 1):
				c[i][j - 1] = 'g'
				d[i][j - 1] = d[i][j] + 1
				q.append((i, j - 1))
			if j + 1 < M and c[i][j + 1] == 'w' and (A[i][j + 1] == 1):
				c[i][j + 1] = 'g'
				d[i][j + 1] = 1 + d[i][j]
				q.append((i, j + 1))
			c[i][j] = 'b'
		if d[X][Y] == 1000000000.0:
			return -1
		return d[X][Y]


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		visited = [[False] * M for i in range(N)]
		queue = deque([(0, 0, 0)])
		visited[0][0] = True
		directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		while queue:
			(row, col, distance) = queue.popleft()
			if row == X and col == Y:
				return distance
			for d in directions:
				new_row = row + d[0]
				new_col = col + d[1]
				if new_row >= 0 and new_row < N and (new_col >= 0) and (new_col < M):
					if A[new_row][new_col] == 1 and (not visited[new_row][new_col]):
						visited[new_row][new_col] = True
						queue.append((new_row, new_col, distance + 1))
		return -1


class Solution:

	def dfs(self, row, column, A, path, distance, N, M):
		if row + 1 < N and path + 1 < distance[row + 1][column] and (A[row + 1][column] == 1):
			distance[row + 1][column] = path + 1
			self.dfs(row + 1, column, A, path + 1, distance, N, M)
		if row - 1 >= 0 and path + 1 < distance[row - 1][column] and (A[row - 1][column] == 1):
			distance[row - 1][column] = path + 1
			self.dfs(row - 1, column, A, path + 1, distance, N, M)
		if column + 1 < M and path + 1 < distance[row][column + 1] and (A[row][column + 1] == 1):
			distance[row][column + 1] = path + 1
			self.dfs(row, column + 1, A, path + 1, distance, N, M)
		if column - 1 >= 0 and path + 1 < distance[row][column - 1] and (A[row][column - 1] == 1):
			distance[row][column - 1] = path + 1
			self.dfs(row, column - 1, A, path + 1, distance, N, M)

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		visited = [[False for i in range(M)] for j in range(N)]
		distance = [[1000 for i in range(M)] for j in range(N)]
		distance[0][0] = 0
		visited = []
		visited.append('0,0')
		path = 0
		while visited:
			(row, column) = visited.pop(0).split(',')
			row = int(row)
			column = int(column)
			if row == X and column == Y:
				break
			if row + 1 < N and distance[row + 1][column] == 1000 and (A[row + 1][column] == 1):
				distance[row + 1][column] = distance[row][column] + 1
				visited.append(str(row + 1) + ',' + str(column))
			if row - 1 >= 0 and distance[row - 1][column] == 1000 and (A[row - 1][column] == 1):
				distance[row - 1][column] = distance[row][column] + 1
				visited.append(str(row - 1) + ',' + str(column))
			if column + 1 < M and distance[row][column + 1] == 1000 and (A[row][column + 1] == 1):
				distance[row][column + 1] = distance[row][column] + 1
				visited.append(str(row) + ',' + str(column + 1))
			if column - 1 >= 0 and distance[row][column - 1] == 1000 and (A[row][column - 1] == 1):
				distance[row][column - 1] = distance[row][column] + 1
				visited.append(str(row) + ',' + str(column - 1))
		if distance[X][Y] == 1000:
			return -1
		return distance[X][Y]


class Solution:

	def shortestDistance(self, n, m, a, x, y):
		if a[0][0] == 0:
			return -1
		que = [[0, 0, 0]]
		dicrow = [-1, 0, 1, 0]
		diccol = [0, 1, 0, -1]
		vis = set()
		vis.add((0, 0))
		while que:
			(row, col, steps) = que.pop(0)
			if row == x and col == y:
				return steps
			for i in range(4):
				nrow = row + dicrow[i]
				ncol = col + diccol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and ((nrow, ncol) not in vis) and (a[nrow][ncol] == 1):
					vis.add((nrow, ncol))
					que.append([nrow, ncol, steps + 1])
		return -1


import queue

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0 or A[X][Y] == 0:
			return -1
		pq = queue.PriorityQueue()
		pq.put([0, [0, 0]])
		dis = []
		for i in range(N):
			dis.append([10 ** 8] * M)
		dis[0][0] = 0
		while pq.qsize():
			(dist, indexes) = pq.get()
			i = indexes[0]
			j = indexes[1]
			if i == X and j == Y:
				return dist
			row = [-1, 0, 1, 0]
			col = [0, 1, 0, -1]
			for m in range(4):
				newrow = row[m] + i
				newcol = col[m] + j
				if 0 <= newrow < N and 0 <= newcol < M and (A[newrow][newcol] != 0):
					if dis[newrow][newcol] > dist + 1:
						dis[newrow][newcol] = 1 + dist
						pq.put([dis[newrow][newcol], [newrow, newcol]])
		return -1


from collections import deque

class Solution:

	def aux_isSafe(self, x, y, m, n, visited, mat):
		if x < 0 or y < 0 or x >= m or (y >= n) or ((x, y) in visited):
			return False
		if mat[x][y] == 0:
			return False
		return True

	def shortestDistance(self, N, M, mat, X, Y):
		(m, n) = (len(mat), len(mat[0]))
		q = deque()
		q.append(((0, 0), 0))
		move_x = [1, -1, 0, 0]
		move_y = [0, 0, 1, -1]
		visited = set()
		if mat[0][0] == 0:
			return -1
		while q:
			(node, dist) = q.popleft()
			(u, v) = node
			if node == (X, Y):
				return dist
			for (x, y) in zip(move_x, move_y):
				if self.aux_isSafe(u + x, v + y, m, n, visited, mat):
					visited.add((u + x, v + y))
					q.append(((u + x, v + y), dist + 1))
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		qu = deque()
		row_move = [-1, 1, 0, 0]
		col_move = [0, 0, -1, 1]
		distance = [[10 ** 5 for i in range(M)] for j in range(N)]
		distance[0][0] = 0
		qu.append([0, 0])
		A[0][0] = -1
		while qu:
			nd = qu.popleft()
			for i in range(4):
				if 0 <= nd[0] + row_move[i] < N and 0 <= nd[1] + col_move[i] < M and (A[nd[0] + row_move[i]][nd[1] + col_move[i]] != 0):
					if A[nd[0] + row_move[i]][nd[1] + col_move[i]] == 1:
						A[nd[0] + row_move[i]][nd[1] + col_move[i]] = -1
						qu.append([nd[0] + row_move[i], nd[1] + col_move[i]])
					distance[nd[0] + row_move[i]][nd[1] + col_move[i]] = min(1 + distance[nd[0]][nd[1]], distance[nd[0] + row_move[i]][nd[1] + col_move[i]])
		return distance[X][Y] if distance[X][Y] != 10 ** 5 else -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		q = []
		q.append([0, [0, 0]])
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		while q:
			it = q.pop(0)
			dis = it[0]
			r = it[1][0]
			c = it[1][1]
			for i in range(4):
				newr = r + dr[i]
				newc = c + dc[i]
				if 0 <= newr < N and 0 <= newc < M and A[newr][newc]:
					if newr == X and newc == Y:
						return dis + 1
					q.append([dis + 1, [newr, newc]])
					A[newr][newc] = 0
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		visited = [[0 for i in range(M)] for j in range(N)]
		visited[0][0] = 1
		q = deque()
		q.append([0, [0, 0]])
		r = [1, -1, 0, 0]
		c = [0, 0, -1, 1]
		while q:
			front = q.popleft()
			dist = front[0]
			row = front[1][0]
			col = front[1][1]
			if row == X and col == Y:
				return dist
			for i in range(4):
				x = row + r[i]
				y = col + c[i]
				if self.isvalid(x, y, A, N):
					if not visited[x][y]:
						if A[x][y] == 1:
							visited[x][y] = 1
							q.append([dist + 1, [x, y]])
		return -1

	def isvalid(self, newx, newy, A, N):
		if newx >= 0 and newx < N and (newy >= 0) and (newy < M):
			return True
		return False


from collections import deque

class Solution:

	def isValid(self, row, col, N, M):
		if row < N and col < M and (row >= 0) and (col >= 0):
			return True
		return False

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		dr = [0, -1, 0, 1]
		dc = [-1, 0, 1, 0]
		q = deque()
		visited = [[0 for i in range(M)] for j in range(N)]
		q.append([0, [0, 0]])
		visited[0][0] = 1
		while q:
			top = q.popleft()
			dist = top[0]
			row = top[1][0]
			col = top[1][1]
			if row == X and col == Y:
				return dist
			for i in range(4):
				adjrow = row + dr[i]
				adjcol = col + dc[i]
				if self.isValid(adjrow, adjcol, N, M):
					if visited[adjrow][adjcol] == 0:
						if A[adjrow][adjcol] == 1:
							q.append([dist + 1, [adjrow, adjcol]])
							visited[adjrow][adjcol] = 1
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, n, m, grid, x, y):
		visited = [[0] * m for _ in range(n)]
		dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		if grid[0][0] == 0:
			return -1
		que = deque([(0, 0, 0)])
		while que:
			(dis, row, col) = que.popleft()
			if row == x and col == y:
				return dis
			for (delRow, delCol) in dirc:
				nr = delRow + row
				nc = delCol + col
				if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (grid[nr][nc] == 1) and (not visited[nr][nc]):
					que.append((dis + 1, nr, nc))
					visited[nr][nc] = 1
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		N -= 1
		M -= 1
		queue = deque()
		queue.append((0, 0))
		while queue:
			(i, j) = queue.popleft()
			if (i, j) == (X, Y):
				return A[i][j] - 1
			if i > 0 and A[i - 1][j] == 1:
				A[i - 1][j] += A[i][j]
				queue.append((i - 1, j))
			if i < N and A[i + 1][j] == 1:
				A[i + 1][j] += A[i][j]
				queue.append((i + 1, j))
			if j > 0 and A[i][j - 1] == 1:
				A[i][j - 1] += A[i][j]
				queue.append((i, j - 1))
			if j < M and A[i][j + 1] == 1:
				A[i][j + 1] += A[i][j]
				queue.append((i, j + 1))
		return -1


from collections import defaultdict

class Solution:

	def D(self):
		return -1

	def shortestDistance(self, N, M, A, X, Y):
		visted = set()
		d = dict()
		if A[0][0] == 0:
			return -1
		for i in range(len(A)):
			for j in range(len(A[0])):
				d[i, j] = float('inf')
		d[0, 0] = 0
		self.Bfs(0, 0, A, visted, d)
		if d[x, y] == float('inf'):
			return -1
		return d[X, Y]

	def safe(self, x, y, gp):
		if x >= 0 and x < len(gp) and (y >= 0) and (y < len(gp[0])) and (gp[x][y] == 1):
			return True
		return False

	def Bfs(self, i, j, gp, visted, d):
		queue = []
		queue.append((i, j))
		visted.add((i, j))
		while len(queue) != 0:
			(i, j) = queue.pop(0)
			List = [(1, 0), (0, 1), (0, -1), (-1, 0)]
			for (a, b) in List:
				saf = self.safe(i + a, j + b, gp)
				if saf == True and (i + a, j + b) not in visted:
					visted.add((i + a, j + b))
					queue.append((i + a, j + b))
					if d[i, j] + 1 < d[i + a, j + b]:
						d[i + a, j + b] = d[i, j] + 1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		R = N
		C = M
		if A[0][0] == 0 or A[X][Y] == 0:
			return -1
		dq = deque([(0, 0)])
		count = 0
		while dq:
			for _ in range(len(dq)):
				(r, c) = dq.popleft()
				if r == X and c == Y:
					return count
				for (dr, dc) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
					(nr, nc) = (r + dr, c + dc)
					if 0 <= nr < R and 0 <= nc < C and (A[nr][nc] == 1):
						A[nr][nc] = 0
						dq.append((nr, nc))
			count += 1
		return -1


from collections import deque
INT_MAX = 4294967296

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		rl = [-1, 1, 0, 0]
		cl = [0, 0, -1, 1]
		if A[0][0] == 0:
			return -1
		else:
			dis = A
			dis[0][0] = 0
			q = deque()
			q.append([0, 0])
			A[0][0] == 0
			while len(q) > 0:
				temp = q.popleft()
				row = temp[0]
				col = temp[1]
				for i in range(4):
					newrow = row + rl[i]
					newcol = col + cl[i]
					if newrow >= 0 and newrow < N and (newcol >= 0) and (newcol < M):
						if A[newrow][newcol] == 1 and newrow == X and (newcol == Y):
							return dis[row][col] + 1
						elif A[newrow][newcol] == 1:
							q.append([newrow, newcol])
							A[newrow][newcol] = 0
							dis[newrow][newcol] = dis[row][col] + 1
			return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		q = []
		vis = [[100000 for _ in range(M)] for _ in range(N)]
		vis[0][0] = 0
		q.append([0, 0, 0])
		res = -1
		while q:
			k = q.pop(0)
			u = k[1]
			v = k[2]
			for (i, j) in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
				nr = i + u
				nc = j + v
				if nr >= 0 and nr < N and (nc >= 0) and (nc < M) and (A[nr][nc] == 1):
					if vis[nr][nc] > 1 + k[0]:
						vis[nr][nc] = 1 + vis[u][v]
						q.append([vis[nr][nc], nr, nc])
						if nr == X and nc == Y:
							return vis[nr][nc]
		return res


class Solution:

	def shortestDistance(self, n, m, A, X, Y):
		poss = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		if not A[0][0]:
			return -1
		visited = [[not A[i][j] for j in range(m)] for i in range(n)]
		q = [[0, 0]]
		visited[0][0] = True
		ptr = 0
		level = 0
		while ptr < len(q):
			if q[ptr] == [X, Y]:
				return level
			for _ in range(len(q) - ptr):
				top = q[ptr]
				ptr += 1
				for i in poss:
					a = top[0] + i[0]
					b = top[1] + i[1]
					if a >= 0 and a < n and (b >= 0) and (b < m) and (not visited[a][b]):
						if [a, b] == [X, Y]:
							return level + 1
						visited[a][b] = True
						q.append([a, b])
			level += 1
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, Y, X):
		if N == 0 or M == 0:
			return -1
		VISITED = -1
		update = True
		d = 0
		q = dict.fromkeys([d + 1], deque())
		if A[0][0] == 1:
			A[0][0] = VISITED
			q[d + 1].append([0, 0])
		else:
			return -1
		while update:
			update = False
			d += 1
			q.setdefault(d + 1, deque())
			while q[d]:
				[i, j] = q[d].pop()
				if i == Y and j == X:
					return d - 1
				for [y, x] in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
					if not (0 <= y < N and 0 <= x < M):
						continue
					if A[y][x] == 1:
						update = True
						A[y][x] = VISITED
						q[d + 1].append([y, x])
		return -1


from collections import deque

class Solution:

	def isValid(self, x, y, n, m):
		return 0 <= x < n and 0 <= y < m

	def shortestDistance(self, N, M, A, X, Y):
		visited = [[False for _ in range(M)] for _ in range(N)]
		distance = [[-1 for _ in range(M)] for _ in range(N)]
		moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		q = deque()
		if A[0][0] == 0:
			return -1
		q.append((0, 0))
		visited[0][0] = True
		distance[0][0] = 0
		while len(q) > 0:
			f = q.popleft()
			if f[0] == X and f[1] == Y:
				break
			for move in moves:
				nx = f[0] + move[0]
				ny = f[1] + move[1]
				if not self.isValid(nx, ny, N, M):
					continue
				if visited[nx][ny]:
					continue
				if A[nx][ny] == 1:
					distance[nx][ny] = distance[f[0]][f[1]] + 1
					visited[nx][ny] = True
					q.append((nx, ny))
		return distance[X][Y]


import math
from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		dis = [[math.inf] * M for i in range(N)]
		q = deque()
		q.append((0, 0, 0))
		dis[0][0] = 0
		while q:
			(r, c, d) = q.popleft()
			for (u, v) in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
				nr = r + u
				nc = c + v
				if nr > -1 and nc > -1 and (nr < N) and (nc < M) and (A[nr][nc] == 1) and (dis[nr][nc] > d + 1):
					dis[nr][nc] = d + 1
					q.append((nr, nc, dis[nr][nc]))
		if dis[X][Y] == math.inf:
			return -1
		return dis[X][Y]


import collections

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 1:
			queue = collections.deque([[0, 0, 0]])
		else:
			return -1
		visited = []
		for i in range(0, N):
			visited.append([-1] * M)
		visited[0][0] = 0
		self.traverse(A, visited, X, Y, queue, M, N)
		return visited[X][Y]

	def traverse(self, a, visited, x, y, queue, m, n):
		while queue:
			temp = queue.popleft()
			if temp[0] == x and temp[1] == y:
				break
			if temp[0] - 1 >= 0:
				if a[temp[0] - 1][temp[1]] == 1 and visited[temp[0] - 1][temp[1]] == -1:
					visited[temp[0] - 1][temp[1]] = temp[2] + 1
					queue.append([temp[0] - 1, temp[1], temp[2] + 1])
			if temp[0] + 1 < n:
				if a[temp[0] + 1][temp[1]] == 1 and visited[temp[0] + 1][temp[1]] == -1:
					visited[temp[0] + 1][temp[1]] = temp[2] + 1
					queue.append([temp[0] + 1, temp[1], temp[2] + 1])
			if temp[1] - 1 >= 0:
				if a[temp[0]][temp[1] - 1] == 1 and visited[temp[0]][temp[1] - 1] == -1:
					visited[temp[0]][temp[1] - 1] = temp[2] + 1
					queue.append([temp[0], temp[1] - 1, temp[2] + 1])
			if temp[1] + 1 < m:
				if a[temp[0]][temp[1] + 1] == 1 and visited[temp[0]][temp[1] + 1] == -1:
					visited[temp[0]][temp[1] + 1] = temp[2] + 1
					queue.append([temp[0], temp[1] + 1, temp[2] + 1])
		return


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		dr = [1, -1, 0, 0]
		dc = [0, 0, 1, -1]
		Q = deque()
		Q.append([0, 0, 0])
		visit = [[False for c in range(M)] for r in range(N)]
		while Q:
			(r, c, d) = Q.popleft()
			if r < 0 or r >= N or c < 0 or (c >= M) or (A[r][c] == 0) or visit[r][c]:
				continue
			if r == X and c == Y:
				return d
			visit[r][c] = True
			for i in range(4):
				(nr, nc) = (r + dr[i], c + dc[i])
				if (nr >= 0 and nr < N and (nc >= 0) and (nc < M)) and visit[nr][nc] == False:
					Q.append([nr, nc, d + 1])
		return -1


from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

def util(board, n, m, sr, sc, dr, dc, mem):
	if sr < 0 or sr >= n or sc < 0 or (sc >= m):
		return float('inf')
	if board[sr][sc] == 0:
		return float('inf')
	if mem[sr][sc] != -1:
		return mem[sr][sc]
	if sr == dr and sc == dc:
		return 0
	mem[sr][sc] = float('inf')
	mem[sr][sc] = min(util(board, n, m, sr + 1, sc, dr, dc, mem), util(board, n, m, sr - 1, sc, dr, dc, mem), util(board, n, m, sr, sc + 1, dr, dc, mem), util(board, n, m, sr, sc - 1, dr, dc, mem)) + 1
	return mem[sr][sc]

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		dr = [1, -1, 0, 0]
		dc = [0, 0, 1, -1]
		Q = deque()
		Q.append([0, 0, 0])
		visit = [[False for c in range(M)] for r in range(N)]
		while Q:
			(r, c, d) = Q.popleft()
			if r < 0 or r >= N or c < 0 or (c >= M) or (A[r][c] == 0) or visit[r][c]:
				continue
			if r == X and c == Y:
				return d
			visit[r][c] = True
			for i in range(4):
				(nr, nc) = (r + dr[i], c + dc[i])
				if (nr >= 0 and nr < N and (nc >= 0) and (nc < M)) and visit[nr][nc] == False:
					Q.append([nr, nc, d + 1])
		return -1


class Solution:

	def neighbours(self, N, M, A, x, y):
		neighb = []
		if x > 0 and A[x - 1][y] == 1:
			neighb.append((x - 1, y))
		if y > 0 and A[x][y - 1] == 1:
			neighb.append((x, y - 1))
		if x < N - 1 and A[x + 1][y] == 1:
			neighb.append((x + 1, y))
		if y < M - 1 and A[x][y + 1] == 1:
			neighb.append((x, y + 1))
		return neighb

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		visited = [[False for _ in range(M)] for _ in range(N)]
		queue = [(0, 0, 0)]
		visited[0][0] = True
		for (x, y, steps) in queue:
			neighb = self.neighbours(N, M, A, x, y)
			for (x_n, y_n) in neighb:
				if x_n == X and y_n == Y:
					return steps + 1
				if not visited[x_n][y_n]:
					visited[x_n][y_n] = True
					queue.append((x_n, y_n, steps + 1))
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		visited = [[False for _ in range(M)] for _ in range(N)]
		level = 0
		visited[0][0] = True
		que = deque([(0, 0)])
		while que:
			for _ in range(len(que)):
				(ci, cj) = que.popleft()
				if ci == X and cj == Y:
					return level
				for (ni, nj) in self.get_nbrs(ci, cj, N, M):
					if not visited[ni][nj] and A[ni][nj] == 1:
						que.append((ni, nj))
						visited[ni][nj] = True
			level += 1
		return -1

	def get_nbrs(self, pi, pj, m, n):
		res = []
		for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			ni = pi + di
			nj = pj + dj
			if 0 <= ni < m and 0 <= nj < n:
				res.append((ni, nj))
		return res


from collections import deque

class point:

	def __init__(self, x, y, d):
		self.x = x
		self.y = y
		self.d = d

def bfs(graph, tx, ty):
	que = deque()
	p1 = point(0, 0, 0)
	que.append(p1)
	visited = [[0] * len(graph[0]) for i in range(len(graph))]
	visited[0][0] = True
	while que:
		p = que.popleft()
		if p.x == tx and p.y == ty:
			return p.d
		if p.x - 1 >= 0 and (not visited[p.x - 1][p.y]) and graph[p.x - 1][p.y]:
			p1 = point(p.x - 1, p.y, p.d + 1)
			que.append(p1)
			visited[p.x - 1][p.y] = True
		if p.x + 1 < len(graph) and (not visited[p.x + 1][p.y]) and graph[p.x + 1][p.y]:
			p1 = point(p.x + 1, p.y, p.d + 1)
			que.append(p1)
			visited[p.x + 1][p.y] = True
		if p.y - 1 >= 0 and (not visited[p.x][p.y - 1]) and graph[p.x][p.y - 1]:
			p1 = point(p.x, p.y - 1, p.d + 1)
			que.append(p1)
			visited[p.x][p.y - 1] = True
		if p.y + 1 < len(graph[0]) and (not visited[p.x][p.y + 1]) and graph[p.x][p.y + 1]:
			p1 = point(p.x, p.y + 1, p.d + 1)
			que.append(p1)
			visited[p.x][p.y + 1] = True
	return -1

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		return bfs(A, X, Y)


from queue import Queue

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		q = Queue()
		q.put((0, 0))
		visited = [[False] * M for _ in range(N)]
		visited[0][0] = True
		dist = [[0] * M for _ in range(N)]
		while not q.empty():
			(i, j) = q.get()
			for move in moves:
				(move_i, move_j) = (i + move[0], j + move[1])
				if 0 <= move_i < N and 0 <= move_j < M:
					if not visited[move_i][move_j] and A[move_i][move_j] == 1:
						visited[move_i][move_j] = True
						q.put((move_i, move_j))
						dist[move_i][move_j] = dist[i][j] + 1
						if move_i == X and move_j == Y:
							return dist[move_i][move_j]
		return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		from collections import deque
		visited = set()
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		q = deque()
		q.append((0, 0))
		steps = 0
		found = False
		while q:
			for i in range(len(q)):
				(currX, currY) = q.popleft()
				if currX not in range(N) or currY not in range(M) or A[currX][currY] == 0 or ((currX, currY) in visited):
					continue
				elif (currX, currY) == (X, Y):
					found = True
					break
				else:
					visited.add((currX, currY))
					for (a, b) in directions:
						q.append((currX + a, currY + b))
			if found:
				break
			steps += 1
		return steps if found else -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		dis = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		if A[0][0] == 0:
			return -1
		st = deque([(0, 0, 0)])
		while st:
			n = len(st)
			while n:
				n -= 1
				(i, j, lvl) = st.popleft()
				if i == X and j == Y:
					return lvl
				else:
					for t in dis:
						x = i + t[0]
						y = j + t[1]
						if 0 <= x < N and 0 <= y < M and (A[x][y] == 1):
							st.append((x, y, lvl + 1))
							A[x][y] = 0
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		visited = [[-1] * M for _ in range(N)]
		q = deque([(0, 0)])
		visited[0][0] = 0
		while q:
			current = q.popleft()
			(row, col) = current
			cells = [(row, col - 1), (row, col + 1), (row - 1, col), (row + 1, col)]
			for (nrow, ncol) in cells:
				if 0 <= nrow < N and 0 <= ncol < M and (visited[nrow][ncol] == -1) and (A[nrow][ncol] == 1):
					visited[nrow][ncol] = visited[row][col] + 1
					q.append((nrow, ncol))
		return visited[X][Y]


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		rows = N
		cols = M
		if rows == 0:
			return -1
		if A[0][0] == 0 or A[X][Y] == 0:
			return -1
		dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]
		q = []
		q.append((0, 0, 0))
		while q:
			(curr_cost, row, col) = q.pop(0)
			if row == X and col == Y:
				return curr_cost
			for (di, dj) in dir:
				(n_row, n_col) = (row + di, col + dj)
				if n_row >= 0 and n_col >= 0 and (n_row < rows) and (n_col < cols) and A[n_row][n_col]:
					q.append((curr_cost + 1, n_row, n_col))
					A[n_row][n_col] = 0
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		visit = [[0 for _ in range(M)] for _ in range(N)]
		step = 0
		if A[0][0] == 0:
			return -1
		if A[X][Y] == 0:
			return -1
		ans = 1000
		q = deque()
		q.append([[0, 0], 0])
		visit[0][0] = 1
		x = [-1, 0, 1]
		flag = 0
		while q:
			t = q.popleft()
			r = t[0][0]
			c = t[0][1]
			p = t[1]
			if r == X and c == Y:
				flag = 1
				ans = min(ans, p)
			for i in x:
				new_r = r + i
				if new_r >= 0 and new_r < N and (visit[new_r][c] == 0) and (A[new_r][c] == 1):
					q.append([[new_r, c], p + 1])
					visit[new_r][c] = 1
			for i in x:
				new_c = c + i
				if new_c >= 0 and new_c < M and (visit[r][new_c] == 0) and (A[r][new_c] == 1):
					q.append([[r, new_c], p + 1])
					visit[r][new_c] = 1
		if flag == 1:
			return ans
		else:
			return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		q = deque()
		if A[0][0] == 0:
			return -1
		q.appendleft((0, 0, 0))
		while q:
			(time, i, j) = q.pop()
			A[i][j] = 2
			if i == X and j == Y:
				return time
			if i + 1 < N and A[i + 1][j] == 1:
				A[i + 1][j] = 2
				q.appendleft((time + 1, i + 1, j))
			if i - 1 >= 0 and A[i - 1][j] == 1:
				A[i - 1][j] = 2
				q.appendleft((time + 1, i - 1, j))
			if j + 1 < M and A[i][j + 1] == 1:
				A[i][j + 1] = 2
				q.appendleft((time + 1, i, j + 1))
			if j - 1 >= 0 and A[i][j - 1] == 1:
				A[i][j - 1] = 2
				q.appendleft((time + 1, i, j - 1))
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, n, m, a, x, y):
		if a[0][0] == 0:
			return -1
		queue = deque()
		queue.append((0, 0))
		path = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		ans = 0
		visit = set()
		visit.add((0, 0))

		def isvalid(i, j):
			if 0 <= i < n and 0 <= j < m and (a[i][j] == 1) and ((i, j) not in visit):
				return True
			return False
		while queue:
			k = len(queue)
			for _ in range(k):
				(i, j) = queue.popleft()
				if i == x and j == y:
					return ans
				for (di, dj) in path:
					(ni, nj) = (i + di, j + dj)
					if isvalid(ni, nj):
						visit.add((ni, nj))
						queue.append((ni, nj))
			ans += 1
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, mat, X, Y):
		if not mat or not mat[0] or (not mat[0][0]):
			return -1
		dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		res = [[float('inf')] * M for _ in range(N)]
		ss = deque([(0, 0), (None, None)])
		res[0][0] = 0
		l = 0
		while ss:
			(x, y) = ss.popleft()
			if x == None:
				l += 1
				if ss:
					ss.append((None, None))
				continue
			if x == X and y == Y:
				return l
			for (dx, dy) in dirs:
				(nx, ny) = (x + dx, y + dy)
				if 0 <= nx < N and 0 <= ny < M and (mat[nx][ny] == 1) and (res[nx][ny] > l):
					ss.append((nx, ny))
					res[nx][ny] = l
		return -1


class Solution:

	def CanPushIntoQueue(self, x, y, grid):
		if x < 0 or x >= len(grid) or y < 0 or (y >= len(grid[0])) or (grid[x][y] == -1) or (grid[x][y] == 0):
			return False
		return True

	def ExploreNodeAndPush(self, x, y, desX, desY, grid, q):
		if self.CanPushIntoQueue(x, y, grid):
			if x == desX and y == desY:
				return True
			grid[x][y] = -1
			q.append([x, y])
		return False

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		queue_list = []
		queue_list.append([0, 0])
		A[0][0] = -1
		level = -1
		while len(queue_list) > 0:
			node_at_level = len(queue_list)
			level += 1
			while node_at_level > 0:
				firstNode = queue_list.pop(0)
				xx = firstNode[0]
				yy = firstNode[1]
				if xx == X and yy == Y:
					return level
				if self.ExploreNodeAndPush(xx - 1, yy, X, Y, A, queue_list):
					return level + 1
				if self.ExploreNodeAndPush(xx + 1, yy, X, Y, A, queue_list):
					return level + 1
				if self.ExploreNodeAndPush(xx, yy - 1, X, Y, A, queue_list):
					return level + 1
				if self.ExploreNodeAndPush(xx, yy + 1, X, Y, A, queue_list):
					return level + 1
				node_at_level -= 1
		return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		if A[X][Y] == 0:
			return -1
		if X == 0 and Y == 0:
			return 0

		def neighbours(N, M, arr, ele):

			def isValid(C):
				return C[0] >= 0 and C[0] < N and (C[1] >= 0) and (C[1] < M) and arr[C[0]][C[1]]
			neighbour = []
			e = (ele[0] - 1, ele[1])
			if isValid(e):
				neighbour.append(e)
			e = (ele[0] + 1, ele[1])
			if isValid(e):
				neighbour.append(e)
			e = (ele[0], ele[1] - 1)
			if isValid(e):
				neighbour.append(e)
			e = (ele[0], ele[1] + 1)
			if isValid(e):
				neighbour.append(e)
			return neighbour
		distances = []
		q = set()
		for i in range(N):
			distances.append([])
			for j in range(M):
				distances[i].append(float('inf'))
		q.add((0, (0, 0)))
		while len(q):
			element = q.pop()
			coord = element[1]
			dist = element[0]
			for nbr in neighbours(N, M, A, coord):
				if dist + 1 < distances[nbr[0]][nbr[1]]:
					distances[nbr[0]][nbr[1]] = dist + 1
					q.add((dist + 1, nbr))
		returning = distances[X][Y]
		return returning if returning < float('inf') else -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0 or A[X][Y] == 0:
			return -1
		vis = [[False for i in range(M)] for j in range(N)]
		vis[0][0] = True
		q = deque()
		q.append([0, 0, 0])
		rownum = [-1, 0, 0, 1]
		colnum = [0, -1, 1, 0]

		def isValid(row, col):
			return row >= 0 and row < N and (col >= 0) and (col < M)
		while len(q):
			(i, j, d) = q.popleft()
			if i == X and j == Y:
				return d
			for k in range(4):
				row = i + rownum[k]
				col = j + colnum[k]
				if isValid(row, col) and A[row][col] == 1 and (not vis[row][col]):
					vis[row][col] = True
					q.append([row, col, d + 1])
		return -1


class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		if A[0][0] == 0:
			return -1
		priority_queue = [[0, 0, 0]]

		def values_in_range(num1, num2):
			return num1 >= 0 and num1 < len(A) and (num2 >= 0) and (num2 < len(A[0]))
		list_check = [[1, 0], [0, 1], [-1, 0], [0, -1]]
		found = [[True for _ in range(len(A[0]))] for _ in range(len(A))]
		found[0][0] = False
		while len(priority_queue) > 0:
			(i, j, val) = priority_queue.pop(0)
			for (x, y) in list_check:
				x += i
				y += j
				if values_in_range(x, y) and A[x][y] != 0 and found[x][y]:
					if x == X and y == Y:
						return val + 1
					found[x][y] = False
					priority_queue.append([x, y, val + 1])
		if N == X and M == Y:
			return 0
		return -1


from heapq import heappush, heappop

class Solution:

	def shortestDistance(self, N, M, grid, X, Y):
		if len(grid) == 0 or grid[X][Y] == 0 or grid[0][0] == 0:
			return -1
		vis = set()
		heap = [(0, (0, 0))]
		while heap:
			(cost, pos) = heappop(heap)
			(cr, cc) = (pos[0], pos[1])
			if cr == X and cc == Y:
				return cost
			for (xdir, ydir) in [[cr - 1, cc], [cr + 1, cc], [cr, cc + 1], [cr, cc - 1]]:
				if 0 <= xdir < N and 0 <= ydir < M and (grid[xdir][ydir] == 1) and ((xdir, ydir) not in vis):
					vis.add((xdir, ydir))
					heappush(heap, (cost + 1, (xdir, ydir)))
		return -1


class Solution:

	def shortestDistance(self, row, col, grid, tarX, tarY):
		if not grid[0][0] or not grid[tarX][tarY]:
			return -1
		q = []
		q.append((0, 0, 0))
		grid[0][0] = 0
		for (i, j, d) in q:
			if i == tarX and j == tarY:
				return d
			for (x, y) in [[i - 1, j], [i + 1, j], [i, j + 1], [i, j - 1]]:
				if 0 <= x < row and 0 <= y < col and grid[x][y]:
					grid[x][y] = 0
					q.append((x, y, d + 1))
		return -1


from collections import deque

def isInside(i, j, n, m):
	if i >= 0 and i < n and (j >= 0) and (j < m):
		return True
	return False

def getAvailableNeighbors(i, j, n, m, grid):
	dx = [-1, 1, 0, 0]
	dy = [0, 0, 1, -1]
	avail = []
	for w in range(len(dy)):
		x = i + dx[w]
		y = j + dy[w]
		if isInside(x, y, n, m) and grid[x][y] == 1:
			avail.append((x, y))
	return avail

class Solution:

	def shortestDistance(self, N, M, A, X, Y):
		visited = [[False] * M for i in range(N)]
		if A[0][0] == 0 or A[X][Y] == 0:
			return -1
		q = deque()
		q.append((0, 0, 0))
		while q:
			current = q.popleft()
			if (current[0], current[1]) == (X, Y):
				return current[2]
			neighs = getAvailableNeighbors(current[0], current[1], N, M, A)
			for ne in neighs:
				if not visited[ne[0]][ne[1]]:
					q.append((ne[0], ne[1], current[2] + 1))
					visited[ne[0]][ne[1]] = True
		return -1


class QItem:

	def __init__(self, row, col, dist):
		self.row = row
		self.col = col
		self.dist = dist

class Solution:

	def shortestDistance(self, N, M, a, y, x):
		if a[0][0] == 0:
			return -1
		node = QItem(0, 0, 0)
		visited = [[False for _ in range(len(a[0]))] for _ in range(len(a))]
		queue = []
		queue.append(node)
		visited[0][0] = True
		while queue:
			node = queue.pop(0)
			if node.row == y and node.col == x:
				return node.dist
			if node.row - 1 >= 0 and a[node.row - 1][node.col] == 1 and (not visited[node.row - 1][node.col]):
				queue.append(QItem(node.row - 1, node.col, node.dist + 1))
				visited[node.row - 1][node.col] = True
			if node.row + 1 <= N - 1 and a[node.row + 1][node.col] == 1 and (not visited[node.row + 1][node.col]):
				queue.append(QItem(node.row + 1, node.col, node.dist + 1))
				visited[node.row + 1][node.col] = True
			if node.col + 1 <= M - 1 and a[node.row][node.col + 1] == 1 and (not visited[node.row][node.col + 1]):
				queue.append(QItem(node.row, node.col + 1, node.dist + 1))
				visited[node.row][node.col + 1] = True
			if node.col - 1 >= 0 and a[node.row][node.col - 1] == 1 and (not visited[node.row][node.col - 1]):
				queue.append(QItem(node.row, node.col - 1, node.dist + 1))
				visited[node.row][node.col - 1] = True
		return -1


class Solution:

	def shortestDistance(self, n, m, a, x, y):
		start = (0, 0)
		end = (x, y)
		if a[0][0] == 0:
			return -1
		queue = []
		visited = set()
		count = 0
		queue.append([start, count])
		visited.add(start)
		while queue:
			(y_temp, count) = queue.pop(0)
			(r, c) = y_temp
			if y_temp == end:
				return count
			for (x1, x2) in [(r, c - 1), (r, c + 1), (r + 1, c), (r - 1, c)]:
				if x1 < n and 0 <= x1 and (x2 < m) and (0 <= x2) and (a[x1][x2] == 1):
					if (x1, x2) not in visited:
						visited.add((x1, x2))
						queue.append([(x1, x2), count + 1])
		return -1


from collections import deque

class Solution:

	def shortestDistance(self, N, M, A, X, Y):

		def getAllNeigh(r, c):
			l = []
			if r + 1 < N and A[r + 1][c] == 1:
				l.append([r + 1, c])
			if c + 1 < M and A[r][c + 1] == 1:
				l.append([r, c + 1])
			if r - 1 >= 0 and A[r - 1][c] == 1:
				l.append([r - 1, c])
			if c - 1 >= 0 and A[r][c - 1] == 1:
				l.append([r, c - 1])
			return l
		q = deque()
		(s, d) = ([0, 0], [X, Y])
		if A[0][0] == 0:
			return -1
		visited = set()
		q.append(tuple(s) + (0,))
		visited.add((0, 0))
		while len(q) > 0:
			(r, c, l) = q.popleft()
			if r == X and c == Y:
				return l
			for (x1, x2) in [(r, c - 1), (r, c + 1), (r + 1, c), (r - 1, c)]:
				if x1 >= 0 and x1 < N and (x2 >= 0) and (x2 < M) and (A[x1][x2] == 1):
					if (x1, x2) not in visited:
						q.append((x1, x2) + (l + 1,))
						visited.add((x1, x2))
		return -1