Given an N x M matrix, with a few hurdles(denoted by 0) arbitrarily placed, calculate the length of the longest possible route possible from source(xs,ys) to a destination(xd,yd) within the matrix. We are allowed to move to only adjacent cells which are not hurdles. The route cannot contain any diagonal moves and a location once visited in a particular path cannot be visited again.If it is impossible to reach the destination from the source return -1.
 
Example 1:
Input:
{xs,ys} = {0,0}
{xd,yd} = {1,7}
matrix = 1 1 1 1 1 1 1 1 1 1
         1 1 0 1 1 0 1 1 0 1
         1 1 1 1 1 1 1 1 1 1
Output: 24
Explanation:
 
Example 2:
Input: 
{xs,ys} = {0,3}
{xd,yd} = {2,2}
matrix = 1 0 0 1 0
         0 0 0 1 0
         0 1 1 0 0
Output: -1
Explanation:
We can see that it is impossible to
reach the cell (2,2) from (0,3).
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestPath() which takes matrix ,source and destination as input parameters and returns an integer denoting the longest path.
Expected Time Complexity: O(2^(N*M))
Expected Auxiliary Space: O(N*M)
Constraints:
1 <= N,M <= 10

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Complete search

Starter code: 



class Solution:

    def longestPath(self,mat : List[List[int]],n : int, m : int, xs : int, ys : int, xd : int, yd : int) -> int:

        # code here

        







Solutions:
class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int):
		ans = -1
		dir_x = [0, 0, 1, -1]
		dir_y = [1, -1, 0, 0]

		def isvalid(mat, n, m, xs, ys):
			if xs < 0 or ys < 0:
				return False
			if xs >= n or ys >= m:
				return False
			if mat[xs][ys] != 1:
				return False
			return True

		def solve(mat, n, m, xs, ys, xd, yd, dist):
			nonlocal ans
			if xs == xd and ys == yd:
				ans = max(ans, dist)
				return
			for i in range(4):
				dist += 1
				mat[xs][ys] = -1
				xs += dir_x[i]
				ys += dir_y[i]
				if isvalid(mat, n, m, xs, ys):
					solve(mat, n, m, xs, ys, xd, yd, dist)
				xs -= dir_x[i]
				ys -= dir_y[i]
				mat[xs][ys] = 1
				dist -= 1
		if mat[xs][ys] != 1:
			return -1
		solve(mat, n, m, xs, ys, xd, yd, 0)
		return ans


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:

		def solve(mat, n, m, xs, ys, xd, yd, cnt):
			if xs == xd and yd == ys:
				ans[0] = max(cnt, ans[0])
				return
			dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
			for (i, j) in dir:
				dx = xs + i
				dy = ys + j
				if dx >= 0 and dy >= 0 and (dx <= n - 1) and (dy <= m - 1) and (mat[dx][dy] == 1):
					mat[dx][dy] = 0
					solve(mat, n, m, dx, dy, xd, yd, cnt + 1)
					mat[dx][dy] = 1
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		ans = [-1]
		mat[xs][ys] = 0
		solve(mat, n, m, xs, ys, xd, yd, 0)
		return ans[0]


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):

		def function(i, j, visited, mat, sum1, sum2):
			if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])) or (mat[i][j] == 0):
				return
			if visited[i][j] == 'T':
				return
			if i == xd and j == yd:
				sum2[0] = max(sum2[0], sum1)
				return
			visited[i][j] = 'T'
			function(i + 1, j, visited, mat, sum1 + mat[i][j], sum2)
			function(i - 1, j, visited, mat, sum1 + mat[i][j], sum2)
			function(i, j + 1, visited, mat, sum1 + mat[i][j], sum2)
			function(i, j - 1, visited, mat, sum1 + mat[i][j], sum2)
			visited[i][j] = 'F'
			return
		sum1 = 0
		sum2 = [0]
		visited = [['F' for i in range(len(mat[0]))] for j in range(len(mat))]
		function(xs, ys, visited, mat, sum1, sum2)
		if sum2[0] == 0:
			return -1
		return sum2[0]


import sys
sys.setrecursionlimit(10000)
from typing import List

class Solution:

	def __init__(self):
		self.ans = []

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xd][yd] == 0:
			return -1

		def backtrack(n, m, i, j, dest, count):
			if i == dest[0] and j == dest[1]:
				self.ans.append(count)
				return
			if i < 0 or j < 0 or i >= n or (j >= m) or (mat[i][j] == 0):
				return
			mat[i][j] = 0
			temp = count
			backtrack(n, m, i + 1, j, dest, temp + 1)
			backtrack(n, m, i, j + 1, dest, temp + 1)
			backtrack(n, m, i - 1, j, dest, temp + 1)
			backtrack(n, m, i, j - 1, dest, temp + 1)
			mat[i][j] = 1
			count = temp
		backtrack(n, m, xs, ys, (xd, yd), 0)
		if len(self.ans) == 0:
			return -1
		new = max(self.ans)
		return new


def rec(mat, i, j, visited, xd, yd):
	if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])) or visited[i][j] or (not mat[i][j]):
		return -1
	if i == xd and j == yd:
		return 0
	visited[i][j] = True
	x = [0, 0, 1, -1]
	y = [1, -1, 0, 0]
	ma = -1
	for k in range(4):
		temp = rec(mat, i + x[k], j + y[k], visited, xd, yd)
		if temp != -1:
			ma = max(ma, temp + 1)
	visited[i][j] = False
	return ma

class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		visited = [[False for i in range(m)] for j in range(n)]
		return rec(mat, xs, ys, visited, xd, yd)


class Solution:

	def longestPath(self, matrix, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		currlen = 0

		def safe(matrix, xs, ys):
			if xs < 0 or ys < 0 or xs >= len(matrix) or (ys >= len(matrix[0])) or (matrix[xs][ys] != 1):
				return False
			else:
				return True
		res = 0

		def solve(matrix, xs, ys, xd, yd, currlen, length):
			currlen = max(currlen, length)
			nonlocal res
			if xs == xd and ys == yd:
				res = max(res, currlen)
				return
			if safe(matrix, xs + 1, ys):
				matrix[xs][ys] = 2
				solve(matrix, xs + 1, ys, xd, yd, currlen + 1, length)
				matrix[xs][ys] = 1
			if safe(matrix, xs - 1, ys):
				matrix[xs][ys] = 2
				solve(matrix, xs - 1, ys, xd, yd, currlen + 1, length)
				matrix[xs][ys] = 1
			if safe(matrix, xs, ys + 1):
				matrix[xs][ys] = 2
				solve(matrix, xs, ys + 1, xd, yd, currlen + 1, length)
				matrix[xs][ys] = 1
			if safe(matrix, xs, ys - 1):
				matrix[xs][ys] = 2
				solve(matrix, xs, ys - 1, xd, yd, currlen + 1, length)
				matrix[xs][ys] = 1
		if matrix[xs][ys] == 0 or matrix[xd][yd] == 0:
			return -1
		solve(matrix, xs, ys, xd, yd, currlen, 0)
		return res


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1

		def dfs(r, c, pathLen, ans):
			if r == xd and c == yd:
				ans[0] = max(ans[0], pathLen)
				return
			for (dr, dc) in directions:
				row = r + dr
				col = c + dc
				if row in range(rows) and c in range(cols) and ((r, c) not in visited) and (mat[r][c] == 1):
					visited.add((r, c))
					dfs(row, col, pathLen + 1, ans)
					visited.remove((r, c))
		directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		rows = n
		cols = m
		ans = [-1]
		pathLen = 0
		visited = set()
		dfs(xs, ys, pathLen, ans)
		return ans[0]


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		visited = [[-1] * len(mat[0]) for i in range(len(mat))]

		def traverse(i, j, xd, yd):
			if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])) or (mat[i][j] == 0) or (visited[i][j] == 1):
				return -999999999
			if i == xd and j == yd:
				return 0
			visited[i][j] = 1
			val = -999999999
			val = max(val, 1 + traverse(i + 1, j, xd, yd))
			val = max(val, 1 + traverse(i - 1, j, xd, yd))
			val = max(val, 1 + traverse(i, j + 1, xd, yd))
			val = max(val, 1 + traverse(i, j - 1, xd, yd))
			visited[i][j] = -1
			return val
		val = traverse(xs, ys, xd, yd)
		if val < 0:
			return -1
		else:
			return val


def util(mat, m, n, xs, ys, xd, yd, visit, path):
	if xs == xd and ys == yd:
		return path
	if xs < 0 or xs >= m or ys < 0 or (ys >= n) or (mat[xs][ys] == 0) or visit[xs][ys]:
		return float('inf')
	visit[xs][ys] = True
	dx = [0, 0, 1, -1]
	dy = [1, -1, 0, 0]
	dist = 0
	for i in range(4):
		(x, y) = (xs + dx[i], ys + dy[i])
		t = util(mat, m, n, x, y, xd, yd, visit, path + 1)
		if t != float('inf') and t > dist:
			dist = t
	visit[xs][ys] = False
	return dist

class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xd][yd] == 0:
			return -1
		(m, n) = (len(mat), len(mat[0]))
		visit = [[False for c in range(n)] for r in range(m)]
		ans = util(mat, m, n, xs, ys, xd, yd, visit, 0)
		if ans == float('inf'):
			return -1
		else:
			return ans


from typing import List

class Solution:
	Max = -1

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		vis = []
		self.solve(mat, xd, yd, xs, ys, 0, vis)
		return self.Max

	def safe(self, mat, i, j):
		if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])) or (mat[i][j] == 0):
			return 0
		return 1

	def solve(self, mat, xd, yd, i, j, way, vis):
		if i == xd and j == yd:
			self.Max = max(way, self.Max)
			return
		if not self.safe(mat, i, j) or (i, j) in vis:
			return
		else:
			vis.append((i, j))
			self.solve(mat, xd, yd, i + 1, j, way + 1, vis)
			self.solve(mat, xd, yd, i, j + 1, way + 1, vis)
			self.solve(mat, xd, yd, i - 1, j, way + 1, vis)
			self.solve(mat, xd, yd, i, j - 1, way + 1, vis)
			vis.pop()
			return


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		if mat[xs][ys] == 0:
			return -1
		self.mat = mat
		self.n = n
		self.m = m
		self.ans = 0
		self.xd = xd
		self.yd = yd
		self.move(xs, ys, 1, {(xs, ys): 1})
		return self.ans - 1

	def move(self, i, j, length, visited):
		if i == self.xd and j == self.yd:
			self.ans = max(self.ans, length)
			return
		for (xdash, ydash) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
			if xdash >= 0 and xdash < self.n and (ydash >= 0) and (ydash < self.m) and (self.mat[xdash][ydash] == 1) and ((xdash, ydash) not in visited):
				visited[xdash, ydash] = 1
				self.move(xdash, ydash, length + 1, visited)
				visited.pop((xdash, ydash))
		return


class Solution:

	def rec(self, mat, i, j, n, m, temp, ans, vis, xd, yd):
		if i < 0 or i >= n or j < 0 or (j >= m) or (vis[i][j] == 1) or (mat[i][j] == 0):
			return
		vis[i][j] = 1
		if i == xd and j == yd:
			ans[0] = max(ans[0], temp)
		paths = [[0, 0, 1, -1], [1, -1, 0, 0]]
		for k in range(4):
			self.rec(mat, paths[0][k] + i, paths[1][k] + j, n, m, temp + 1, ans, vis, xd, yd)
		vis[i][j] = 0

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		ans = [-1]
		vis = [[0] * m for i in range(n)]
		self.rec(mat, xs, ys, n, m, 0, ans, vis, xd, yd)
		return ans[0]


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		return self.helper(mat, xs, ys, n - 1, m - 1, (xd, yd), 0) if mat[xs][ys] else -1

	def helper(self, grid, x, y, n, m, end, count):
		if (x, y) == end:
			return count
		matrix = [row.copy() for row in grid]
		matrix[x][y] = 0
		output = -1
		if x > 0 and matrix[x - 1][y]:
			output = max(output, self.helper(matrix, x - 1, y, n, m, end, count + 1))
		if y > 0 and matrix[x][y - 1]:
			output = max(output, self.helper(matrix, x, y - 1, n, m, end, count + 1))
		if x < n and matrix[x + 1][y]:
			output = max(output, self.helper(matrix, x + 1, y, n, m, end, count + 1))
		if y < m and matrix[x][y + 1]:
			output = max(output, self.helper(matrix, x, y + 1, n, m, end, count + 1))
		return output


class Solution:

	def check(self, i, j, n, m, mat):
		if i < n and 0 <= i and (j < m) and (j >= 0) and (mat[i][j] == 1):
			return True
		return False

	def find(self, i, j, x, y, n, m, mat, ans, visited, cnt):
		if i == x and j == y:
			ans[0] = max(ans[0], cnt)
			return
		if self.check(i, j, n, m, mat) == False or visited[i][j] == 1:
			return
		visited[i][j] = 1
		if self.check(i + 1, j, n, m, mat):
			self.find(i + 1, j, x, y, n, m, mat, ans, visited, cnt + 1)
		if self.check(i - 1, j, n, m, mat):
			self.find(i - 1, j, x, y, n, m, mat, ans, visited, cnt + 1)
		if self.check(i, j + 1, n, m, mat):
			self.find(i, j + 1, x, y, n, m, mat, ans, visited, cnt + 1)
		if self.check(i, j - 1, n, m, mat):
			self.find(i, j - 1, x, y, n, m, mat, ans, visited, cnt + 1)
		visited[i][j] = 0

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		ans = [-1]
		visited = [[0 for i in range(100)] for j in range(100)]
		self.find(xs, ys, xd, yd, n, m, mat, ans, visited, 0)
		return ans[0]


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):

		def solve(mat, n, m, xs, ys, xd, yd, count=0):
			if mat[xd][yd] == 0:
				return -1
			if xs == xd and ys == yd:
				return count
			if xs < 0 or xs >= n or ys < 0 or (ys >= m):
				return -1
			if mat[xs][ys] in [0, 2]:
				return -1
			count += 1
			mat[xs][ys] = 2
			res = max(solve(mat, n, m, xs + 1, ys, xd, yd, count), solve(mat, n, m, xs - 1, ys, xd, yd, count), solve(mat, n, m, xs, ys + 1, xd, yd, count), solve(mat, n, m, xs, ys - 1, xd, yd, count))
			mat[xs][ys] = 1
			return res
		return solve(mat, n, m, xs, ys, xd, yd)


from typing import List

class Solution:

	def issafe(self, mat, row, col, n, m):
		return True if row >= 0 and row < n and (col >= 0) and (col < m) and (mat[row][col] == 1) else False

	def find(self, mat, row, col, n, m, xd, yd, length, ans):
		if row == xd and col == yd:
			ans[0] = length if ans[0] < length else ans[0]
			return
		mat[row][col] = -1
		if self.issafe(mat, row, col + 1, n, m):
			self.find(mat, row, col + 1, n, m, xd, yd, length + 1, ans)
		if self.issafe(mat, row, col - 1, n, m):
			self.find(mat, row, col - 1, n, m, xd, yd, length + 1, ans)
		if self.issafe(mat, row - 1, col, n, m):
			self.find(mat, row - 1, col, n, m, xd, yd, length + 1, ans)
		if self.issafe(mat, row + 1, col, n, m):
			self.find(mat, row + 1, col, n, m, xd, yd, length + 1, ans)
		mat[row][col] = 1

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		ans = [0]
		self.find(mat, xs, ys, n, m, xd, yd, 0, ans)
		return ans[0]


def backtracking(xs, ys, n, m, xd, yd, arr):
	if arr[xs][ys] == 0 or arr[xd][yd] == 0:
		return -1
	vis = set()
	vis.add((xs, ys))
	res = []
	helper(xs, ys, n, m, xd, yd, arr, vis, res)
	if res:
		return res[-1] - 1
	return -1

def helper(i, j, r, c, xd, yd, arr, vis, res):
	if (i, j) == (xd, yd):
		if not res:
			res.append(len(vis))
		else:
			res[-1] = max(res[-1], len(tuple(vis)))
	for (ti, tj) in zip([1, -1, 0, 0], [0, 0, 1, -1]):
		(ni, nj) = (ti + i, tj + j)
		if isValid(ni, nj, r, c, arr) and (ni, nj) not in vis:
			vis.add((ni, nj))
			helper(ni, nj, r, c, xd, yd, arr, vis, res)
			vis.remove((ni, nj))

def isValid(i, j, r, c, arr):
	if i >= 0 and i < r and (j >= 0) and (j < c) and arr[i][j]:
		return True
	return False

class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		return backtracking(xs, ys, n, m, xd, yd, mat)


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		ans = -1
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1

		def fun(i, j, path):
			nonlocal ans
			mat[i][j] = 2
			if i == xd and j == yd:
				ans = max(ans, path)
			if i - 1 >= 0:
				if mat[i - 1][j] == 1:
					fun(i - 1, j, path + 1)
			if i + 1 < n:
				if mat[i + 1][j] == 1:
					fun(i + 1, j, path + 1)
			if j - 1 >= 0:
				if mat[i][j - 1] == 1:
					fun(i, j - 1, path + 1)
			if j + 1 < m:
				if mat[i][j + 1] == 1:
					fun(i, j + 1, path + 1)
			mat[i][j] = 1
		fun(xs, ys, 0)
		return ans


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		self.ans = -1
		self.dir_delta = [[0, -1], [-1, 0], [0, 1], [1, 0]]
		R = n
		C = m

		def canGoto(r, c):
			nonlocal mat, R, C
			return 0 <= r < R and 0 <= c < C and (mat[r][c] == 1)

		def backtrack(sr, sc, distance=0):
			nonlocal mat, xd, yd
			if canGoto(sr, sc):
				if sr == xd and sc == yd:
					self.ans = max(self.ans, distance)
				else:
					mat[sr][sc] = 2
					for (dr, dc) in self.dir_delta:
						backtrack(sr + dr, sc + dc, distance + 1)
					mat[sr][sc] = 1
		backtrack(xs, ys)
		return self.ans


class Solution:

	def isValid(self, mat, x, y, n, m):
		if x >= 0 and y >= 0 and (x < n) and (y < m) and (not vis[x][y]) and mat[x][y]:
			return True
		return False

	def solve(self, mat, n, m, x, y, ex, ey, cor, steps):
		global maxi
		if not self.isValid(mat, x, y, n, m):
			return
		if x == ex and y == ey:
			maxi = max(maxi, steps)
			return
		vis[x][y] = 1
		for i in range(4):
			nx = x + cor[i][0]
			ny = y + cor[i][1]
			self.solve(mat, n, m, nx, ny, ex, ey, cor, steps + 1)
		vis[x][y] = 0

	def longestPath(self, mat, n, m, sx, sy, ex, ey):
		if sx == ex and sy == ey:
			return 0
		if not mat[sx][sy]:
			return -1
		global vis
		vis = [[0 for i in range(m)] for j in range(n)]
		global maxi
		maxi = float('-Inf')
		cor = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		self.solve(mat, n, m, sx, sy, ex, ey, cor, 0)
		if maxi == float('-Inf'):
			return -1
		return maxi


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		paths = []
		path = []
		recStack = set()
		recStack.add((xs, ys))

		def dfs(r, c):
			if mat[r][c] == 0:
				return
			if [r, c] == [xd, yd]:
				paths.append(path.copy())
				return
			if r - 1 >= 0 and mat[r - 1][c] == 1 and ((r - 1, c) not in recStack):
				path.append('U')
				recStack.add((r - 1, c))
				dfs(r - 1, c)
				recStack.remove((r - 1, c))
				path.pop()
			if r + 1 < n and mat[r + 1][c] == 1 and ((r + 1, c) not in recStack):
				path.append('D')
				recStack.add((r + 1, c))
				dfs(r + 1, c)
				recStack.remove((r + 1, c))
				path.pop()
			if c - 1 >= 0 and mat[r][c - 1] == 1 and ((r, c - 1) not in recStack):
				path.append('L')
				recStack.add((r, c - 1))
				dfs(r, c - 1)
				recStack.remove((r, c - 1))
				path.pop()
			if c + 1 < m and mat[r][c + 1] == 1 and ((r, c + 1) not in recStack):
				path.append('R')
				recStack.add((r, c + 1))
				dfs(r, c + 1)
				recStack.remove((r, c + 1))
				path.pop()
		dfs(xs, ys)
		mx = -1
		for p in paths:
			mx = max(mx, len(p))
		return mx


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1

		def dfs(r, c, pathlen, res):
			if r == xd and c == yd:
				res[0] = max(res[0], pathlen)
				return
			for (x, y) in directions:
				row = r + x
				col = c + y
				if -1 < row < rows and -1 < col < cols and ((r, c) not in visited) and (mat[r][c] == 1):
					visited.add((r, c))
					dfs(row, col, pathlen + 1, res)
					visited.remove((r, c))
		directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		rows = n
		cols = m
		res = [-1]
		pathlen = 0
		visited = set()
		dfs(xs, ys, pathlen, res)
		return res[0]


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd) -> int:
		res = [0]
		vis = [[0 for i in range(m)] for i in range(n)]
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1

		def recsol(row, col, temp):
			if row == xd and col == yd:
				res[0] = max(res[0], temp)
				return
			if row < 0 or col < 0 or row >= n or (col >= m) or (vis[row][col] == 1) or (mat[row][col] == 0):
				return
			vis[row][col] = 1
			recsol(row + 1, col, temp + 1)
			recsol(row, col + 1, temp + 1)
			recsol(row - 1, col, temp + 1)
			recsol(row, col - 1, temp + 1)
			vis[row][col] = 0
			return
		recsol(xs, ys, 0)
		return res[0]


import sys

class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		visited = [[0 for j in range(m)] for i in range(n)]
		dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]

		def dfs(x, y):
			if x == xd and y == yd:
				return 0
			visited[x][y] = 1
			val = -sys.maxsize
			for (a, b) in dir:
				nx = a + x
				ny = b + y
				if nx < 0 or ny < 0 or nx >= n or (ny >= m) or visited[nx][ny] or (mat[nx][ny] == 0):
					continue
				val = max(val, 1 + dfs(nx, ny))
			visited[x][y] = 0
			return val
		if mat[xs][ys] == 0:
			return -1
		val = dfs(xs, ys)
		if val < 0:
			return -1
		return val


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int):
		visited = [[0 for i in range(m)] for j in range(n)]
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

		def dfs(x, y):
			if x == xd and y == yd:
				return 0
			mn = -float('inf')
			visited[x][y] = 1
			for (i, j) in directions:
				nx = x + i
				ny = y + j
				if nx >= n or nx < 0 or ny >= m or (ny < 0) or visited[nx][ny] or (mat[nx][ny] == 0):
					continue
				mn = max(mn, 1 + dfs(nx, ny))
			visited[x][y] = 0
			return mn
		if mat[xs][ys] == 0:
			return -1
		val = dfs(xs, ys)
		if val == -float('inf'):
			return -1
		return val


class Solution:

	def longestPath(self, M, R, C, sc, sr, dc, dr):
		if M[sc][sr] == 0:
			return -1
		ans = dfs(sc, sr, R, C, M, set(), dr, dc)
		return -1 if ans == 0 else ans

def dfs(r, c, R, C, M, v, dc, dr):
	if (r, c) == (dr, dc):
		return len(v)
	v.add((r, c))
	l = 0
	for (nr, nc) in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
		if 0 <= nr < R and 0 <= nc < C and ((nr, nc) not in v) and (M[nr][nc] == 1):
			l = max(l, dfs(nr, nc, R, C, M, v, dc, dr))
	v.remove((r, c))
	return l


from typing import List

class Solution:

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		self.ans = -1
		vis = [[0 for i in range(m)] for j in range(n)]

		def sol(i, j, xd, yd, mat, vis, length):
			if i == xd and j == yd:
				self.ans = max(length, self.ans)
				return
			dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
			for idx in range(len(dirs)):
				(newx, newy) = (i + dirs[idx][0], j + dirs[idx][1])
				if 0 <= newx < len(mat) and 0 <= newy < len(mat[0]) and (mat[newx][newy] == 1) and (vis[newx][newy] == 0):
					vis[i][j] = 1
					sol(newx, newy, xd, yd, mat, vis, length + 1)
					vis[i][j] = 0
			return
		sol(xs, ys, xd, yd, mat, vis, 0)
		return self.ans


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1

		def sol(mat, i, j, xd, yd, length):
			if i == xd and j == yd:
				if length > self.ans:
					self.ans = length
				return
			dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
			for idx in range(len(dirs)):
				(newx, newy) = (i + dirs[idx][0], j + dirs[idx][1])
				if 0 <= newx < len(mat) and 0 <= newy < len(mat[0]) and (mat[newx][newy] == 1):
					mat[i][j] = 2
					sol(mat, newx, newy, xd, yd, length + 1)
					mat[i][j] = 1
			return
		self.ans = -1
		sol(mat, xs, ys, xd, yd, 0)
		return self.ans


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		if xs == xd and ys == yd:
			return 0
		vis = [[0 for i in range(m)] for j in range(n)]

		def dfs(grid, sr, sc, dr, dc, vis, n, m, ans, cnt):
			if sr == dr and sc == dc:
				ans[0] = max(ans[0], cnt)
				return
			if sr < 0 or sc < 0 or sr >= n or (sc >= m) or (vis[sr][sc] == 1) or (grid[sr][sc] == 0):
				return
			vis[sr][sc] = 1
			dfs(grid, sr + 1, sc, dr, dc, vis, n, m, ans, cnt + 1)
			dfs(grid, sr - 1, sc, dr, dc, vis, n, m, ans, cnt + 1)
			dfs(grid, sr, sc + 1, dr, dc, vis, n, m, ans, cnt + 1)
			dfs(grid, sr, sc - 1, dr, dc, vis, n, m, ans, cnt + 1)
			vis[sr][sc] = 0
		ans = [-1]
		cnt = 0
		dfs(mat, xs, ys, xd, yd, vis, n, m, ans, cnt)
		return ans[0]


from typing import List

class Solution:

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		is_valid = lambda x: 0 <= x[1] < m and 0 <= x[0] < n and mat[x[0]][x[1]]
		ans = [-1]
		visited = set()

		def rec(cell, l):
			if cell == (xd, yd):
				ans[0] = max(ans[0], l)
				return
			visited.add(cell)
			neighbours = [(cell[0] - 1, cell[1]), (cell[0] + 1, cell[1]), (cell[0], cell[1] - 1), (cell[0], cell[1] + 1)]
			for ncell in neighbours:
				if is_valid(ncell) and ncell not in visited:
					rec(ncell, l + 1)
			visited.remove(cell)
		if mat[xs][ys]:
			rec((xs, ys), 0)
		return ans[0]


from typing import List

class Solution:

	def helper(self, xs, ys, xd, yd, count):
		if xs == xd and ys == yd:
			self.count = max(self.count, count)
			return
		self.mat[xs][ys] = 0
		for (x1, y1) in self.next:
			(x2, y2) = (xs + x1, ys + y1)
			if -1 < x2 < self.n and -1 < y2 < self.m and (self.mat[x2][y2] == 1):
				self.helper(x2, y2, xd, yd, count + 1)
		self.mat[xs][ys] = 1

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		if xs == xd and ys == yd:
			return 0
		self.next = [[-1, 0], [0, -1], [0, 1], [1, 0]]
		self.count = -1
		self.mat = mat
		(self.n, self.m) = (n, m)
		self.helper(xs, ys, xd, yd, 0)
		return self.count

class Solution1:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1

		def dfs(r, c, pathLen, ans):
			if r == xd and c == yd:
				ans[0] = max(ans[0], pathLen)
				return
			for (dr, dc) in directions:
				row = r + dr
				col = c + dc
				if row in range(rows) and c in range(cols) and ((r, c) not in visited) and (mat[r][c] == 1):
					visited.add((r, c))
					dfs(row, col, pathLen + 1, ans)
					visited.remove((r, c))
		directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		rows = n
		cols = m
		ans = [-1]
		pathLen = 0
		visited = set()
		dfs(xs, ys, pathLen, ans)
		return ans[0]

class Solution1:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:

		def solve(mat, n, m, xs, ys, xd, yd, cnt):
			if xs == xd and yd == ys:
				ans[0] = max(cnt, ans[0])
				return
			dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
			for (i, j) in dir:
				dx = xs + i
				dy = ys + j
				if dx >= 0 and dy >= 0 and (dx <= n - 1) and (dy <= m - 1) and (mat[dx][dy] == 1):
					mat[dx][dy] = 0
					solve(mat, n, m, dx, dy, xd, yd, cnt + 1)
					mat[dx][dy] = 1
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		if xs == xd and ys == yd:
			return 0
		ans = [-1]
		mat[xs][ys] = 0
		solve(mat, n, m, xs, ys, xd, yd, 0)
		return ans[0]


from typing import List
INT_MIN = -(1 << 63)

class Solution:

	def is_valid(self, row, col, n, m, mat, visited):
		if row >= 0 and row < n and (col >= 0) and (col < m) and (mat[row][col] == 1) and (not visited[row][col]):
			return True
		return False

	def longest_path_util(self, row, col, path_len, mat, visited, n, m, xd, yd, max_len):
		if xd == row and yd == col:
			if path_len > max_len[0]:
				max_len[0] = path_len
			return
		dxy = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		for (dx, dy) in dxy:
			n_row = row + dx
			n_col = col + dy
			if self.is_valid(n_row, n_col, n, m, mat, visited):
				visited[n_row][n_col] = True
				self.longest_path_util(n_row, n_col, path_len + 1, mat, visited, n, m, xd, yd, max_len)
				visited[n_row][n_col] = False

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0:
			return -1
		max_len = [-1]
		visited = [[False for _ in range(m)] for _ in range(n)]
		visited[xs][ys] = True
		self.longest_path_util(xs, ys, 0, mat, visited, n, m, xd, yd, max_len)
		return max_len[0]


from typing import List

class Solution:

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		self.ans = 0
		self.dist = 0

		def dfs(i, j):
			if i < 0 or i >= n or j < 0 or (j >= m):
				return
			if mat[i][j] == 0 or mat[i][j] == -1:
				return
			if i == xd and j == yd:
				self.ans = max(self.dist, self.ans)
			mat[i][j] = -1
			self.dist += 1
			dfs(i + 1, j)
			dfs(i - 1, j)
			dfs(i, j + 1)
			dfs(i, j - 1)
			mat[i][j] = 1
			self.dist -= 1
		dfs(xs, ys)
		return self.ans


class Solution:

	def solve(self, mat, i, j, m, n, dp, c, ans):
		if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])) or (mat[i][j] == 0) or (dp[i][j] == False):
			return -100000000
		if i == n and j == m:
			return 0
		dp[i][j] = False
		ans = 1 + max(self.solve(mat, i + 1, j, m, n, dp, c + 1, ans), self.solve(mat, i, j + 1, m, n, dp, c + 1, ans), self.solve(mat, i - 1, j, m, n, dp, c + 1, ans), self.solve(mat, i, j - 1, m, n, dp, c + 1, ans))
		dp[i][j] = True
		return ans

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		dp = [[True for i in range(m)] for j in range(n)]
		ans = self.solve(mat, xs, ys, yd, xd, dp, 0, 0)
		if ans < 0:
			return -1
		return ans


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		if mat[xs][ys] == 0:
			return -1
		vis = [[False for _ in range(m)] for _ in range(n)]
		mat[xs][ys] = -1
		mx = [-1]
		self.fn(mat, n, m, xs, ys, xd, yd, 0, vis, mx)
		return max(mx)

	def fn(self, mat, n, m, xs, ys, xd, yd, path, vis, mx):
		if xs == xd and ys == yd:
			mx.append(path)
			return
		for (i, j) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
			if 0 <= xs + i < n and 0 <= ys + j < m and (mat[xs + i][ys + j] == 1):
				mat[xs + i][ys + j] = -1
				self.fn(mat, n, m, xs + i, ys + j, xd, yd, path + 1, vis, mx)
				mat[xs + i][ys + j] = 1


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:

		def solve(mat, n, m, xs, ys, xd, yd, temp):
			if xs < 0 or ys < 0 or xs == n or (ys == m) or (mat[xs][ys] == 2) or (mat[xs][ys] == 0):
				return
			nonlocal length
			if xs == xd and ys == yd:
				if temp > length:
					length = temp
				return
			mat[xs][ys] = 2
			solve(mat, n, m, xs - 1, ys, xd, yd, temp + 1)
			solve(mat, n, m, xs + 1, ys, xd, yd, temp + 1)
			solve(mat, n, m, xs, ys + 1, xd, yd, temp + 1)
			solve(mat, n, m, xs, ys - 1, xd, yd, temp + 1)
			mat[xs][ys] = 1
		length = -1
		solve(mat, n, m, xs, ys, xd, yd, 0)
		return length


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		ans = []
		visited = [[0 for _ in range(m)] for _ in range(n)]

		def isSafe(x, y):
			if x >= 0 and y >= 0 and (x < n) and (y < m) and (visited[x][y] != 1) and (mat[x][y] == 1):
				return True
			return False

		def solve(x, y, path):
			if x == xd and y == yd:
				ans.append(path)
				return
			visited[x][y] = 1
			if isSafe(x + 1, y):
				solve(x + 1, y, path + 1)
			if isSafe(x, y - 1):
				solve(x, y - 1, path + 1)
			if isSafe(x, y + 1):
				solve(x, y + 1, path + 1)
			if isSafe(x - 1, y):
				solve(x - 1, y, path + 1)
			visited[x][y] = 0
		if mat[xs][ys] == 0:
			return -1
		else:
			solve(xs, ys, 0)
			if ans:
				return max(ans)
			else:
				return -1


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		res = [0]

		def dfs(r, c, path):
			if r == xd and c == yd:
				res[0] = max(res[0], path)
				return
			directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]
			visited[r][c] = 1
			for (dr, dc) in directions:
				(i, j) = (dr + r, dc + c)
				if i >= 0 and i < n and (j >= 0) and (j < m) and (mat[i][j] == 1) and (visited[i][j] == 0):
					dfs(i, j, path + 1)
			visited[r][c] = 0
		visited = [[0 for i in range(m)] for j in range(n)]
		dfs(xs, ys, 0)
		if res[0] == 0:
			return -1
		return res[0]


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		n = len(mat)
		m = len(mat[0])
		ans = -1

		def dfs(i, j, visited, dist):
			nonlocal ans
			move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
			if mat[i][j] == 0 or (i, j) in visited:
				return
			if (i, j) == (xd, yd):
				ans = max(ans, dist)
				return
			visited.add((i, j))
			for (x, y) in move:
				newX = x + i
				newY = y + j
				if newX >= 0 and newX < n and (newY >= 0) and (newY < m) and (mat[newX][newY] == 1):
					dfs(newX, newY, visited, dist + 1)
			visited.remove((i, j))
			return ans
		ans = dfs(xs, ys, set(), 0)
		if ans == None:
			return -1
		return ans


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		ans = [-1]

		def f(x, y, xd, yd, mat, n, m, vis, ans, path):
			if x < 0 or x >= n or y < 0 or (y >= m) or vis[x][y] or (mat[x][y] == 0):
				return
			if x == xd and y == yd:
				ans[0] = max(ans[0], path)
				return
			vis[x][y] = 1
			f(x + 1, y, xd, yd, mat, n, m, vis, ans, path + 1)
			f(x - 1, y, xd, yd, mat, n, m, vis, ans, path + 1)
			f(x, y + 1, xd, yd, mat, n, m, vis, ans, path + 1)
			f(x, y - 1, xd, yd, mat, n, m, vis, ans, path + 1)
			vis[x][y] = 0
		vis = [[0] * m for i in range(n)]
		f(xs, ys, xd, yd, mat, n, m, vis, ans, 0)
		return ans[0]


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		ans = -1

		def dfs(x, y, visited, dist):
			nonlocal ans
			if mat[x][y] == 0 or (x, y) in visited:
				return
			if (x, y) == (xd, yd):
				ans = max(dist, ans)
				return
			visited.add((x, y))
			for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				nx = x + dx
				ny = y + dy
				if 0 <= nx < n and 0 <= ny < m:
					dfs(nx, ny, visited, dist + 1)
			visited.remove((x, y))
		dfs(xs, ys, set(), 0)
		return ans


from typing import List

class Solution:

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:

		def solve(i, j, c):
			global ans
			if i < 0 or j < 0 or j >= m or (i >= n) or (not mat[i][j]):
				return
			if i == xd and j == yd:
				ans = max(ans, c)
				return
			mat[i][j] = 0
			solve(i, j - 1, c + 1)
			solve(i, j + 1, c + 1)
			solve(i - 1, j, c + 1)
			solve(i + 1, j, c + 1)
			mat[i][j] = 1
		global ans
		ans = -1
		solve(xs, ys, 0)
		return ans


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:

		def check(mat, n, m, x, y, vis):
			if x >= 0 and y >= 0 and (x < n) and (y < m) and (vis[x][y] == 0):
				return True
			return False

		def recur(mat, n, m, xs, ys, xd, yd, vis, r, c):
			if mat[xs][ys] == 0:
				return -1
			if xs == xd and ys == yd:
				return 0
			vis[xs][ys] = 1
			res = -1
			for i in range(4):
				if check(mat, n, m, xs + r[i], ys + c[i], vis):
					val = recur(mat, n, m, xs + r[i], ys + c[i], xd, yd, vis, r, c)
					if val != -1:
						res = max(val + 1, res)
			vis[xs][ys] = 0
			return res
		vis = [[0 for i in range(m)] for j in range(n)]
		r = [1, 0, 0, -1]
		c = [0, -1, 1, 0]
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		ans = recur(mat, n, m, xs, ys, xd, yd, vis, r, c)
		return ans


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:

		def check(mat, n, m, i, j, vis):
			if i >= 0 and j >= 0 and (i < n) and (j < m) and (vis[i][j] == 0):
				return True
			return False

		def recur(mat, n, m, xs, ys, xd, yd, vis, rh, ch):
			if mat[xs][ys] == 0:
				return -1
			if xs == xd and ys == yd:
				return 0
			vis[xs][ys] = 1
			res = -1
			for i in range(4):
				x = xs + rh[i]
				y = ys + ch[i]
				if check(mat, n, m, x, y, vis):
					mxl = recur(mat, n, m, x, y, xd, yd, vis, rh, ch)
					if mxl != -1:
						res = max(res, mxl + 1)
			vis[xs][ys] = 0
			return res
		vis = [[0 for i in range(m)] for j in range(n)]
		rh = [-1, 0, 0, 1]
		ch = [0, -1, 1, 0]
		ans = recur(mat, n, m, xs, ys, xd, yd, vis, rh, ch)
		return ans


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		path_lengths = []
		visited = set()
		pos = (xs, ys)
		dst = (xd, yd)
		length = 0
		self.dfs(mat, n, m, pos, dst, visited, length, path_lengths)
		if len(path_lengths) == 0:
			return -1
		return max(path_lengths)

	def dfs(self, mat, n, m, pos, dst, visited, length, path_lengths):
		if mat[pos[0]][pos[1]] == 0:
			return
		if pos in visited:
			return
		if pos == dst:
			path_lengths.append(length)
			return
		visited.add(pos)
		if pos[1] < m - 1:
			right_pos = (pos[0], pos[1] + 1)
			self.dfs(mat, n, m, right_pos, dst, visited.copy(), length + 1, path_lengths)
		if pos[0] < n - 1:
			down_pos = (pos[0] + 1, pos[1])
			self.dfs(mat, n, m, down_pos, dst, visited.copy(), length + 1, path_lengths)
		if pos[1] > 0:
			left_pos = (pos[0], pos[1] - 1)
			self.dfs(mat, n, m, left_pos, dst, visited.copy(), length + 1, path_lengths)
		if pos[0] > 0:
			up_pos = (pos[0] - 1, pos[1])
			self.dfs(mat, n, m, up_pos, dst, visited.copy(), length + 1, path_lengths)


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		visited = [[0 for i in range(m)] for i in range(n)]
		ds = ''
		ans = [-1]
		xMoves = [1, 0, 0, -1]
		yMoves = [0, 1, -1, 0]
		dir = 'DLRU'

		def solve(i, j, ds):
			if i == xd and j == yd:
				ans[0] = max(ans[0], len(ds))
				return
			for k in range(4):
				nI = i + xMoves[k]
				nJ = j + yMoves[k]
				if nI >= 0 and nJ >= 0 and (nI < n) and (nJ < m) and (visited[nI][nJ] != 1) and (mat[nI][nJ] == 1):
					visited[nI][nJ] = 1
					solve(nI, nJ, ds + dir[k])
					visited[nI][nJ] = 0
		if mat[xs][ys] == 1:
			visited[xs][ys] = 1
			solve(xs, ys, ds)
		return ans[0]


class Solution:

	def utils(self, mat, n, m, src_row, src_col, dest_row, dest_col, max_path, cur_path):
		if src_col == dest_col and src_row == dest_row:
			max_path[0] = max(max_path[0], path)
			return 0
		if (src_col >= m or src_row >= n) or (src_row < 0 or src_col < 0) or mat[src_row][src_col] == 0:
			return 0
		mat[src_row][src_col] = 0
		self.utils(mat, n, m, src_row + 1, src_col, dest_row, dest_col, max_path, cur_path + 1)
		self.utils(mat, n, m, src_row - 1, src_col, dest_row, dest_col, max_path, cur_path + 1)
		self.utils(mat, n, m, src_row, src_col + 1, dest_row, dest_col, max_path, cur_path + 1)
		self.utils(mat, n, m, src_row, src_col - 1, dest_row, dest_col, max_path, cur_path + 1)
		mat[src_row][src_col] = 1
		return 0

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		ans = -1

		def dfs(x, y, visited, dist):
			nonlocal ans
			if mat[x][y] == 0 or (x, y) in visited:
				return
			if (x, y) == (xd, yd):
				ans = max(dist, ans)
				return
			visited.add((x, y))
			for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				nx = x + dx
				ny = y + dy
				if 0 <= nx < n and 0 <= ny < m:
					dfs(nx, ny, visited, dist + 1)
			visited.remove((x, y))
		dfs(xs, ys, set(), 0)
		return ans


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		path = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		visit = [[0] * m for i in range(n)]

		def f(i, j, count):
			nonlocal maxi
			if i == xd and j == yd:
				maxi = max(maxi, count)
				return
			for (di, dj) in path:
				(ni, nj) = (i + di, j + dj)
				if 0 <= ni < n and 0 <= nj < m and (visit[ni][nj] == 0) and (mat[ni][nj] == 1):
					visit[ni][nj] = 1
					f(ni, nj, count + 1)
					visit[ni][nj] = 0
		maxi = -1
		visit[xs][ys] = 1
		f(xs, ys, 0)
		return maxi


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		ans = -1

		def dfs(x, y, visited, dist):
			nonlocal ans
			if mat[x][y] == 0 or (x, y) in visited:
				return
			if (x, y) == (xd, yd):
				ans = max(dist, ans)
				return
			visited.add((x, y))
			for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				nx = x + dx
				ny = y + dy
				if 0 <= nx < n and 0 <= ny < m:
					dfs(nx, ny, visited, dist + 1)
			visited.remove((x, y))
		dfs(xs, ys, set(), 0)
		return ans

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		b = IntArray().Input(4)
		mat = IntMatrix().Input(a[0], a[0])
		obj = Solution()
		res = obj.longestPath(mat, a[0], a[1], b[0], b[1], b[2], b[3])
		print(res)


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int):
		visited = [[0 for i in range(m)] for j in range(n)]
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

		def dfs(x, y):
			if x == xd and y == yd:
				return 0
			mn = -float('inf')
			visited[x][y] = 1
			for (i, j) in directions:
				nx = x + i
				ny = y + j
				if nx >= n or nx < 0 or ny >= m or (ny < 0) or visited[nx][ny] or (mat[nx][ny] == 0):
					continue
				mn = max(mn, 1 + dfs(nx, ny))
			visited[x][y] = 0
			return mn
		if mat[xs][ys] == 0:
			return -1
		val = dfs(xs, ys)
		if val == -float('inf'):
			return -1
		return val

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		b = IntArray().Input(4)
		mat = IntMatrix().Input(a[0], a[0])
		obj = Solution()
		res = obj.longestPath(mat, a[0], a[1], b[0], b[1], b[2], b[3])
		print(res)


class Solution:

	def longestPath(self, arr, n, m, xs, ys, xd, yd) -> int:
		if arr[xd][yd] == 0:
			return -1

		def helper(i, j):
			if i == xd and j == yd:
				return 0
			if i < 0 or i >= n or j < 0 or (j >= m) or (arr[i][j] == 0):
				return -100000
			arr[i][j] = 0
			val = 1 + max(helper(i + 1, j), helper(i, j + 1), helper(i - 1, j), helper(i, j - 1))
			arr[i][j] = 1
			return val
		res = helper(xs, ys)
		if res < 0:
			return -1
		return res

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		b = IntArray().Input(4)
		mat = IntMatrix().Input(a[0], a[0])
		obj = Solution()
		res = obj.longestPath(mat, a[0], a[1], b[0], b[1], b[2], b[3])
		print(res)


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):

		def haha(arr, i, j, p, q):
			if i == p and j == q:
				return 0
			if i < 0 or j < 0 or i >= n or (j >= m) or (arr[i][j] == 0):
				return float('-inf')
			ma = arr[i][j]
			arr[i][j] = 0
			a = haha(arr, i + 1, j, p, q)
			b = haha(arr, i, j + 1, p, q)
			c = haha(arr, i - 1, j, p, q)
			d = haha(arr, i, j - 1, p, q)
			arr[i][j] = ma
			return 1 + max(a, b, c, d)
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		x = haha(mat, xs, ys, xd, yd)
		if x == float('-inf'):
			return -1
		return x

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		b = IntArray().Input(4)
		mat = IntMatrix().Input(a[0], a[0])
		obj = Solution()
		res = obj.longestPath(mat, a[0], a[1], b[0], b[1], b[2], b[3])
		print(res)


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):

		def haha(arr, i, j, p, q):
			if i == p and j == q:
				return 0
			if i < 0 or j < 0 or i >= n or (j >= m) or (arr[i][j] == 0):
				return float('-inf')
			ma = arr[i][j]
			arr[i][j] = 0
			a = haha(arr, i + 1, j, p, q)
			b = haha(arr, i, j + 1, p, q)
			c = haha(arr, i - 1, j, p, q)
			d = haha(arr, i, j - 1, p, q)
			arr[i][j] = ma
			return 1 + max(a, b, c, d)
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		x = haha(mat, xs, ys, xd, yd)
		if x == float('-inf'):
			return -1
		return x


class Solution:

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1

		def fun(i, j):
			if i == xd and j == yd:
				return 0
			if i < 0 or i >= n or j < 0 or (j >= m) or (mat[i][j] == 0):
				return float('-inf')
			mat[i][j] = 0
			x = 1 + max(fun(i + 1, j), fun(i - 1, j), fun(i, j + 1), fun(i, j - 1))
			mat[i][j] = 1
			return x
		x = fun(xs, ys)
		if x > 0:
			return x
		return -1


class Solution:

	def isBound(self, x, y):
		if 0 <= x < self.N and 0 <= y < self.M:
			return True
		return False

	def dfs(self, x, y, dist):
		if x == self.targetX and y == self.targetY:
			self.maxLength = max(self.maxLength, dist)
			return
		self.mat[x][y] = 0
		for (delX, delY) in zip(self.dx, self.dy):
			newX = x + delX
			newY = y + delY
			if not self.isBound(newX, newY):
				continue
			if self.mat[newX][newY] == 0:
				continue
			self.dfs(newX, newY, dist + 1)
		self.mat[x][y] = 1

	def longestPath(self, mat, n, m, xs, ys, xd, yd):
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		self.dx = [1, -1, 0, 0]
		self.dy = [0, 0, 1, -1]
		(self.N, self.M) = (n, m)
		self.maxLength = -1
		self.mat = mat
		(self.targetX, self.targetY) = (xd, yd)
		self.dfs(xs, ys, 0)
		return self.maxLength


class Solution:

	def longestPath(self, l, n, m, xs, ys, xd, yd):
		if l[xs][ys] == 0 or l[xd][yd] == 0:
			return -1
		self.ans = -1

		def ss(i, j, t):
			if i == xd and j == yd:
				self.ans = max(self.ans, t)
				return
			if i < 0 or j < 0 or i >= n or (j >= m) or (l[i][j] == 0):
				return
			l[i][j] = 0
			ss(i + 1, j, t + 1)
			ss(i - 1, j, t + 1)
			ss(i, j + 1, t + 1)
			ss(i, j - 1, t + 1)
			l[i][j] = 1
		ss(xs, ys, 0)
		return self.ans


from typing import List

class Solution:

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		ans = []

		def traversePath(i, j, path, ans):
			if i == xd and j == yd and (mat[i][j] == 1):
				path.append([i, j])
				ans.append(len(path.copy()))
				path.pop()
			elif i >= len(mat) or j >= len(mat[0]) or i < 0 or (j < 0):
				return
			elif [i, j] not in path and mat[i][j] == 1:
				path.append([i, j])
				traversePath(i + 1, j, path, ans)
				traversePath(i - 1, j, path, ans)
				traversePath(i, j + 1, path, ans)
				traversePath(i, j - 1, path, ans)
				path.pop()
		traversePath(xs, ys, [], ans)
		if len(ans) >= 1:
			return max(ans) - 1
		else:
			return -1


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		ans = -1
		dx = [1, -1, 0, 0]
		dy = [0, 0, 1, -1]

		def rec(i, j, path=0):
			nonlocal ans, xd, yd
			if i < 0 or j < 0 or i >= n or (j >= m):
				return
			if mat[i][j] == 0:
				return
			if i == xd and j == yd:
				ans = max(ans, path)
				return
			mat[i][j] = 0
			for k in range(4):
				x = i + dx[k]
				y = j + dy[k]
				rec(x, y, path + 1)
			mat[i][j] = 1
		rec(xs, ys)
		return ans


class Solution:

	def is_safe(self, x, y, r, c, mat):
		global vis
		if x < 0 or x >= r or y < 0 or (y >= c):
			return False
		return mat[x][y] == 1 and vis[x][y] == False

	def bt(self, cur_x, cur_y, xd, yd, r, c, dist, mat):
		global ans, vis
		if cur_x == xd and cur_y == yd:
			ans = max(ans, dist)
			return
		vis[cur_x][cur_y] = True
		x = [0, 0, -1, 1]
		y = [-1, 1, 0, 0]
		for i in range(len(x)):
			new_x = cur_x + x[i]
			new_y = cur_y + y[i]
			if self.is_safe(new_x, new_y, r, c, mat):
				self.bt(new_x, new_y, xd, yd, r, c, dist + 1, mat)
		vis[cur_x][cur_y] = False

	def longestPath(self, mat, r, c, xs, ys, xd, yd):
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		global ans, vis
		ans = 0
		vis = [[False for j in range(c)] for i in range(r)]
		self.bt(xs, ys, xd, yd, r, c, 0, mat)
		return ans


class Solution:

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		row = len(mat)
		col = len(mat[0])
		ans = []
		visited = [[False] * col for i in range(row)]

		def solve(i, j, c, visited):
			if i < 0 or j < 0 or j >= col or (i >= row) or (mat[i][j] == 0) or (visited[i][j] == True):
				return
			if i == xd and j == yd:
				ans.append(c)
				return
			visited[i][j] = True
			solve(i + 1, j, c + 1, visited)
			solve(i - 1, j, c + 1, visited)
			solve(i, j - 1, c + 1, visited)
			solve(i, j + 1, c + 1, visited)
			visited[i][j] = False
		solve(xs, ys, 0, visited)
		if len(ans) == 0:
			return -1
		return max(ans)


class Solution:

	def __longestPathHelper(self, matrix, path, n, m, x, y, xd, yd):
		self.visited.add((x, y))
		for (x_offset, y_offset) in self.dirs:
			(temp_x, temp_y) = (x + x_offset, y + y_offset)
			if 0 <= temp_x < n and 0 <= temp_y < m and ((temp_x, temp_y) not in self.visited) and (matrix[temp_x][temp_y] != 0):
				if temp_x == xd and temp_y == yd:
					self.ans = max(self.ans, path + 1)
				else:
					self.__longestPathHelper(matrix, path + 1, n, m, temp_x, temp_y, xd, yd)
		self.visited.discard((x, y))

	def longestPath(self, matrix, n, m, xs, ys, xd, yd):
		if matrix[xs][ys] == 0:
			return -1
		(self.visited, self.ans) = (set(), -1)
		self.dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		self.__longestPathHelper(matrix, 0, n, m, xs, ys, xd, yd)
		return self.ans


class Solution:

	def __init__(self):
		self.ans = -1

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int):
		rows = len(mat)
		cols = len(mat[0])
		v2 = [[False for _ in range(cols)] for _ in range(rows)]
		self.path(xs, ys, xd, yd, mat, v2, 0)
		return self.ans

	def path(self, i, j, end_i, end_j, mat, visited, steps):
		if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])) or (visited[i][j] is True) or (mat[i][j] == 0):
			return
		if i == end_i and j == end_j:
			self.ans = max(self.ans, steps)
			return
		visited[i][j] = True
		(self.path(i + 1, j, end_i, end_j, mat, visited, steps + 1),)
		self.path(i, j + 1, end_i, end_j, mat, visited, steps + 1)
		self.path(i - 1, j, end_i, end_j, mat, visited, steps + 1)
		self.path(i, j - 1, end_i, end_j, mat, visited, steps + 1)
		visited[i][j] = False
		return


class Solution:

	def longestPath(self, matrix, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if matrix[xs][ys] == 0 or matrix[xd][yd] == 0:
			return -1
		visited = [[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
		self.res = 0
		r = len(matrix)
		c = len(matrix[0])

		def dfs(i, j, ans):
			if i < 0 or j < 0 or i >= r or (j >= c) or (matrix[i][j] == 0) or (visited[i][j] == True):
				return
			if i == xd and j == yd:
				self.res = max(self.res, ans)
			visited[i][j] = True
			dfs(i + 1, j, ans + 1)
			dfs(i, j + 1, ans + 1)
			dfs(i - 1, j, ans + 1)
			dfs(i, j - 1, ans + 1)
			visited[i][j] = False
		dfs(xs, ys, 0)
		return self.res


import math

class Solution:
	max_val = -1

	def longestPathUtil(self, mat, n, m, xs, ys, xd, yd, curr_val):
		if xs == xd and ys == yd:
			if curr_val > self.max_val:
				self.max_val = curr_val
		dx = [1, 0, 0, -1]
		dy = [0, 1, -1, 0]
		for i in range(4):
			x_new = xs + dx[i]
			y_new = ys + dy[i]
			if x_new >= 0 and x_new <= n - 1 and (y_new >= 0) and (y_new <= m - 1) and (mat[x_new][y_new] == 1):
				mat[x_new][y_new] = 2
				self.longestPathUtil(mat, n, m, x_new, y_new, xd, yd, curr_val + 1)
				mat[x_new][y_new] = 1

	def longestPath(self, mat, n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		mat[xs][ys] = 2
		self.longestPathUtil(mat, n, m, xs, ys, xd, yd, 0)
		return self.max_val


from typing import List
ans = 0

class Solution:

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		vis = set()
		cnt = 0
		if mat[xs][ys] == 0 or mat[xd][yd] == 0:
			return -1
		global ans
		ans = 0

		def isvalid(i, j):
			if 0 <= i < len(mat) and 0 <= j < len(mat[0]) and (mat[i][j] == 1):
				return True
			return False

		def dfs(x, y, cnt):
			global ans
			if (x, y) == (xd, yd):
				ans = max(ans, cnt)
			vis.add((x, y))
			dire = [(1, 0), (0, 1), (-1, 0), (0, -1)]
			for (dx, dy) in dire:
				(xn, yn) = (x + dx, y + dy)
				if isvalid(xn, yn) and (xn, yn) not in vis:
					dfs(xn, yn, cnt + 1)
			vis.remove((x, y))
		dfs(xs, ys, 0)
		return ans


from typing import List
mx = -1

class Solution:

	def all_possible(self, src, visited, mat, dest, sm, neigh, n, m):
		global mx
		if src[0] == dest[0] and src[1] == dest[1]:
			if mx < sm:
				mx = sm
			return
		visited[src[0]][src[1]] = 1
		for i in neigh:
			if src[0] + i[0] >= 0 and src[0] + i[0] < n and (src[1] + i[1] >= 0) and (src[1] + i[1] < m):
				res = [src[0] + i[0], src[1] + i[1]]
				if visited[res[0]][res[1]] == 0 and mat[res[0]][res[1]] > 0:
					self.all_possible(res, visited, mat, dest, sm + mat[res[0]][res[1]], neigh, n, m)
		visited[src[0]][src[1]] = 0

	def longestPath(self, mat: List[List[int]], n: int, m: int, xs: int, ys: int, xd: int, yd: int) -> int:
		global mx
		mx = -1
		neigh = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		src = [xs, ys]
		if mat[xs][ys] == 0:
			return mx
		dest = [xd, yd]
		visited = []
		for i in range(n):
			x = []
			for j in range(m):
				x.append(0)
			visited.append(x)
		self.all_possible(src, visited, mat, dest, 0, neigh, n, m)
		return mx


class Solution:

	def longestPath(self, mat, n, m, xs: int, ys: int, xd: int, yd: int) -> int:
		if not mat:
			return mat
		if mat[xs][ys] == 0:
			return -1
		visited = set()
		(rows, cols) = (len(mat), len(mat[0]))
		ans = []
		visited = set()

		def dfs(i, j, path, visited):
			if i == xd and j == yd:
				ans.append(path)
				return
			if (i + 1, j) not in visited and i + 1 >= 0 and (i + 1 < rows) and (j >= 0) and (j < cols) and (mat[i + 1][j] == 1):
				visited.add((i, j))
				dfs(i + 1, j, path + 'D', visited)
				visited.remove((i, j))
			if (i - 1, j) not in visited and i - 1 >= 0 and (i - 1 < rows) and (j >= 0) and (j < cols) and (mat[i - 1][j] == 1):
				visited.add((i, j))
				dfs(i - 1, j, path + 'U', visited)
				visited.remove((i, j))
			if (i, j - 1) not in visited and i >= 0 and (i < rows) and (j - 1 >= 0) and (j - 1 < cols) and (mat[i][j - 1] == 1):
				visited.add((i, j))
				dfs(i, j - 1, path + 'L', visited)
				visited.remove((i, j))
			if (i, j + 1) not in visited and i >= 0 and (i < rows) and (j + 1 >= 0) and (j + 1 < cols) and (mat[i][j + 1] == 1):
				visited.add((i, j))
				dfs(i, j + 1, path + 'R', visited)
				visited.remove((i, j))
		dfs(xs, ys, '', visited)
		if len(ans) == 0:
			return -1
		maxi = len(ans[0])
		for i in range(len(ans)):
			maxi = max(maxi, len(ans[i]))
		return maxi