Given a grid of size n*n filled with 0, 1, 2, 3. Check whether there is a path possible from the source to destination. You can traverse up, down, right and left.
The description of cells is as follows:
A value of cell 1 means Source.
A value of cell 2 means Destination.
A value of cell 3 means Blank cell.
A value of cell 0 means Wall.
Note: There are only a single source and a single destination.
 
Example 1:
Input: grid = {{3,0,3,0,0},{3,0,0,0,3}
,{3,3,3,3,3},{0,2,3,0,0},{3,0,0,1,3}}
Output: 0
Explanation: The grid is-
3 0 3 0 0 
3 0 0 0 3 
3 3 3 3 3 
0 2 3 0 0 
3 0 0 1 3 
There is no path to reach at (3,1) i,e at 
destination from (4,3) i,e source.
Example 2:
Input: grid = {{1,3},{3,2}}
Output: 1
Explanation: The grid is-
1 3
3 2
There is a path from (0,0) i,e source to (1,1) 
i,e destination.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function is_Possible() which takes the grid as input parameter and returns boolean value 1 if there is a path otherwise returns 0.
 
Expected Time Complexity: O(n^{2})
Expected Auxiliary Space: O(n^{2})
 
Constraints:
1 ≤ n ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Graph algorithms

Data structures

Graph traversal

Starter code: 

class Solution:

    

    #Function to find whether a path exists from the source to destination.

	def is_Possible(self, grid):

		#Code here

Solutions:
class Solution:

	def dfs(self, i, j, visited, grid):
		n = len(grid)
		m = len(grid[0])
		if i >= n or j >= m or i < 0 or (j < 0):
			return False
		if grid[i][j] == 0:
			return False
		if visited[i][j] != 0:
			return False
		if grid[i][j] == 2:
			return True
		if visited[i][j] == 0:
			visited[i][j] = 1
			d1 = self.dfs(i, j + 1, visited, grid)
			d2 = self.dfs(i, j - 1, visited, grid)
			d3 = self.dfs(i + 1, j, visited, grid)
			d4 = self.dfs(i - 1, j, visited, grid)
		return d1 or d2 or d3 or d4

	def is_Possible(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					if self.dfs(i, j, visited, grid) == True:
						return True
		return False


class Solution:

	def is_Possible(self, grid):
		(s, d) = ([], [])
		(m, n) = (len(grid[0]), len(grid))
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					s = [i, j]
					break

		def helper(i, j):
			if i < 0 or n <= i or j < 0 or (m <= j) or (grid[i][j] < 1):
				return False
			if grid[i][j] == 2:
				return True
			grid[i][j] = -1
			for (y, x) in ((i, j + 1), (i + 1, j), (i, j - 1), (i - 1, j)):
				if helper(y, x):
					return True
			return False
		return helper(s[0], s[1])


from collections import *

class Solution:

	def is_Possible(self, grid):

		def isvalid(p, q):
			return 0 <= p < n and 0 <= q < m and (grid[p][q] in [2, 3]) and ((p, q) not in visited)
		(n, m) = (len(grid), len(grid[0]))
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					src = (i, j)
				if grid[i][j] == 2:
					dest = (i, j)
		visited = set()
		qu = deque([src])
		while qu:
			(x, y) = qu.popleft()
			if dest == (x, y):
				return True
			visited.add((x, y))
			for (dx, dy) in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
				if isvalid(x + dx, y + dy):
					visited.add((x + dx, y + dy))
					qu.append((x + dx, y + dy))
		return False


from queue import deque

class Solution:

	def is_Possible(self, grid):
		directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				if grid[row][col] == 1:
					q = deque()
					q.append((row, col))
					grid[row][col] = 0
					while q:
						(currRow, currCol) = q.popleft()
						for dir in directions:
							newRow = currRow + dir[0]
							newCol = currCol + dir[1]
							if newRow >= 0 and newRow < len(grid) and (newCol >= 0) and (newCol < len(grid[0])) and (grid[newRow][newCol] == 2):
								return 1
							if newRow >= 0 and newRow < len(grid) and (newCol >= 0) and (newCol < len(grid[0])) and (grid[newRow][newCol] == 3):
								q.append((newRow, newCol))
								grid[newRow][newCol] = 0
		return 0


from collections import deque

class Solution:

	def is_Possible(self, grid):
		ROWS = len(grid)
		COLS = len(grid[0])
		queue = deque()
		for i in range(ROWS):
			for j in range(COLS):
				if grid[i][j] == 1:
					queue.append([i, j])
		while queue:
			(x, y) = queue.popleft()
			if grid[x][y] == 0:
				continue
			if grid[x][y] == 2:
				return 1
			grid[x][y] = 0
			for (i, j) in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
				if 0 <= x + i < ROWS and 0 <= y + j < COLS and (grid[x + i][y + j] != 0):
					queue.append([x + i, y + j])
		return 0


from collections import deque

class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		source = 0
		dest = 0
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					source = (i, j)
				elif grid[i][j] == 2:
					dest = (i, j)
			if source and dest:
				break
		visited = set()
		q = deque([source])
		while q:
			curr = q.popleft()
			if curr == dest:
				return True
			visited.add(curr)
			for neighbor in self.get_neighbors(curr, grid):
				if neighbor not in visited:
					q.append(neighbor)
		return False

	def get_neighbors(self, cell, grid):
		n = len(grid)
		(row, col) = cell
		neighbors = []
		if row > 0 and grid[row - 1][col] != 0:
			neighbors.append((row - 1, col))
		if row < n - 1 and grid[row + 1][col] != 0:
			neighbors.append((row + 1, col))
		if col > 0 and grid[row][col - 1] != 0:
			neighbors.append((row, col - 1))
		if col < n - 1 and grid[row][col + 1] != 0:
			neighbors.append((row, col + 1))
		return neighbors


class Solution:

	def is_Possible(self, grid):
		v = [[0 for i in range(len(grid))] for j in range(len(grid))]
		res = [False]

		def findPath(i, j):
			if i >= len(grid) or j >= len(grid) or i < 0 or (j < 0) or res[0]:
				return
			if v[i][j] == 1:
				return
			v[i][j] = 1
			if grid[i][j] == 0:
				return
			if grid[i][j] == 2:
				res[0] = True
			findPath(i + 1, j)
			findPath(i - 1, j)
			findPath(i, j + 1)
			findPath(i, j - 1)
		for i in range(len(grid)):
			for j in range(len(grid)):
				if grid[i][j] == 1:
					findPath(i, j)
		return res[0]


class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		visited = [[False for _ in range(n)] for _ in range(n)]

		def dfs(row, col):
			if row < 0 or row >= n or col < 0 or (col >= n) or visited[row][col]:
				return False
			visited[row][col] = True
			if grid[row][col] == 2:
				return True
			if grid[row][col] == 3 or grid[row][col] == 1:
				return dfs(row - 1, col) or dfs(row + 1, col) or dfs(row, col - 1) or dfs(row, col + 1)
			return False
		source_row = 0
		source_col = 0
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					source_row = i
					source_col = j
					break
		return dfs(source_row, source_col)


class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		(src_i, src_j, dest_i, dest_j) = (-1, -1, -1, -1)
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					(src_i, src_j) = (i, j)
				elif grid[i][j] == 2:
					(dest_i, dest_j) = (i, j)
		visited = [[False for j in range(n)] for i in range(n)]

		def is_valid(i, j):
			return i >= 0 and i < n and (j >= 0) and (j < n) and (not visited[i][j]) and (grid[i][j] != 0)
		q = []
		q.append((src_i, src_j))
		visited[src_i][src_j] = True
		while q:
			(i, j) = q.pop(0)
			if i == dest_i and j == dest_j:
				return True
			if is_valid(i + 1, j):
				q.append((i + 1, j))
				visited[i + 1][j] = True
			if is_valid(i - 1, j):
				q.append((i - 1, j))
				visited[i - 1][j] = True
			if is_valid(i, j + 1):
				q.append((i, j + 1))
				visited[i][j + 1] = True
			if is_valid(i, j - 1):
				q.append((i, j - 1))
				visited[i][j - 1] = True
		return False


class Solution:

	def is_Possible(self, grid):
		source = []
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if grid[i][j] == 1:
					source.append([i, j])
		row = [-1, 0, 0, 1]
		col = [0, -1, 1, 0]
		n = len(grid)
		m = len(grid[0])
		while source:
			(r, c) = source.pop()
			for i in range(4):
				rowc = r + row[i]
				colc = c + col[i]
				if rowc < 0 or rowc > n - 1 or colc < 0 or (colc > m - 1) or (grid[rowc][colc] == 1):
					continue
				if grid[rowc][colc] == 3:
					grid[rowc][colc] = 1
					source.append([rowc, colc])
				if grid[rowc][colc] == 2:
					return 1
		return 0


class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		m = len(grid[0])

		def find(i, j, grid):
			if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])) or (grid[i][j] == 0):
				return False
			if grid[i][j] == 2:
				return True
			grid[i][j] = 0
			return find(i + 1, j, grid) or find(i - 1, j, grid) or find(i, j - 1, grid) or find(i, j + 1, grid)
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					return find(i, j, grid)


class Solution:

	def is_Possible(self, grid):
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 2:
					dr = i
					dc = j
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					sr = i
					sc = j
		ch = False

		def helper(sr, sc):
			nonlocal ch
			if sr < 0 or sr >= len(grid) or sc < 0 or (sc >= len(grid[0])):
				return
			if sr == dr and sc == dc:
				ch = True
				return
			if grid[sr][sc] == 0:
				return
			grid[sr][sc] = 0
			helper(sr - 1, sc)
			helper(sr + 1, sc)
			helper(sr, sc - 1)
			helper(sr, sc + 1)
		helper(sr, sc)
		if ch:
			return 1
		else:
			return 0


def issafe(i, j, grid, visited):
	if i >= 0 and i < len(grid) and (j >= 0) and (j < len(grid)):
		return True
	return False

def checkvis(i, j, grid, visited):
	if issafe(i, j, grid, visited) and grid[i][j] != 0 and (not visited[i][j]):
		visited[i][j] = True
		if grid[i][j] == 2:
			return True
		up = checkvis(i - 1, j, grid, visited)
		if up:
			return True
		left = checkvis(i, j - 1, grid, visited)
		if left:
			return True
		down = checkvis(i + 1, j, grid, visited)
		if down:
			return True
		right = checkvis(i, j + 1, grid, visited)
		if right:
			return True
	return False

class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		visited = [[False for x in range(n)] for y in range(n)]
		flag = False
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1 and (not visited[i][j]):
					if checkvis(i, j, grid, visited) == True:
						flag = True
						break
		if flag == True:
			return 1
		else:
			return 0


import sys
sys.setrecursionlimit(501)

class Solution:

	def is_Possible(self, grid):
		flag = [0]
		n = len(grid)
		arr = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					(src_i, src_j) = (i, j)
					break
		self.helper(grid, src_i, src_j, n, flag, arr)
		return flag[0]

	def helper(self, grid, i, j, n, flag, arr):
		if i < 0 or i >= n:
			return
		if j < 0 or j >= n:
			return
		if arr[i][j] == 1:
			return
		if grid[i][j] == 0:
			return
		if grid[i][j] == 2:
			flag[0] = 1
			return
		arr[i][j] = 1
		self.helper(grid, i + 1, j, n, flag, arr)
		self.helper(grid, i - 1, j, n, flag, arr)
		self.helper(grid, i, j + 1, n, flag, arr)
		self.helper(grid, i, j - 1, n, flag, arr)


from collections import deque

class Solution:

	def is_Possible(self, grid):
		(s, d) = ([], [])
		(n, m) = (len(grid), len(grid[0]))
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					s = [i, j]
				elif grid[i][j] == 2:
					d = [i, j]
		visit = [[0] * m for _ in range(n)]
		q = deque()
		if s < d:
			q.append((s[0], s[1]))
			while q:
				(r, c) = q.popleft()
				visit[r][c] = 1
				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 (grid[nr][nc] != 0) and (not visit[nr][nc]):
						if [nr, nc] == d:
							return 1
						q.append((nr, nc))
		elif s > d:
			q.append((d[0], d[1]))
			while q:
				(r, c) = q.popleft()
				visit[r][c] = 1
				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 (grid[nr][nc] != 0) and (not visit[nr][nc]):
						if [nr, nc] == s:
							return 1
						q.append((nr, nc))
		return 0


dirx = [1, 0, 0, -1]
diry = [0, 1, -1, 0]

class Solution:

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

	def dfs(self, grid, vis, x, y):
		if grid[x][y] == 2:
			return True
		vis[x][y] = True
		for i in range(4):
			new_x = x + dirx[i]
			new_y = y + diry[i]
			if self.valid(grid, new_x, new_y, vis) and self.dfs(grid, vis, new_x, new_y):
				return True
		return False

	def is_Possible(self, grid):
		n = len(grid)
		m = len(grid[0])
		(x, y) = (-1, -1)
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					(x, y) = (i, j)
		vis = [[False for j in range(m)] for i in range(n)]
		b = self.dfs(grid, vis, x, y)
		if b == True:
			return 1
		else:
			return 0


class Solution:

	def util(self, a, i, j, n, m):
		global dp
		if i < 0 or j < 0 or j >= m or (i >= n) or (a[i][j] == 0):
			return 0
		if a[i][j] == 2:
			return 1
		if dp[i][j] != -1:
			return dp[i][j]
		if a[i][j] == 1:
			dp[i][j] = self.util(a, i + 1, j, n, m) | self.util(a, i - 1, j, n, m) | self.util(a, i, j + 1, n, m) | self.util(a, i, j - 1, n, m)
			return dp[i][j]
		else:
			a[i][j] = 0
			dp[i][j] = self.util(a, i + 1, j, n, m) | self.util(a, i - 1, j, n, m) | self.util(a, i, j + 1, n, m) | self.util(a, i, j - 1, n, m)
			return dp[i][j]
			a[i][j] = 3

	def is_Possible(self, grid):
		n = len(grid)
		m = len(grid[0])
		global dp
		dp = [[-1 for i in range(n)] for j in range(m)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					return self.util(grid, i, j, n, m)


class Solution:
	di = [(0, 1), (0, -1), (1, 0), (-1, 0)]

	def find_first(grid):
		for x in range(len(grid)):
			for y in range(len(grid[0])):
				if grid[x][y] == 1:
					return (x, y, 2)
				elif grid[x][y] == 2:
					return (x, y, 1)

	def solver(gird, x, y, dest):
		for d in Solution.di:
			new_x = x + d[0]
			new_y = y + d[1]
			if new_x < 0 or new_x >= len(grid) or new_y < 0 or (new_y >= len(grid[0])):
				continue
			if gird[new_x][new_y] == dest:
				return True
			elif gird[new_x][new_y] == 3:
				grid[new_x][new_y] = 10
				if Solution.solver(grid, new_x, new_y, dest):
					return True
				gird[new_x][new_y] = 3
		return False

	def is_Possible(self, grid):
		(x, y, dest) = Solution.find_first(grid)
		if Solution.solver(grid, x, y, dest):
			return True
		return False


class Solution:

	def is_Possible(self, grid):

		def dfs(i, j):
			if i < 0 or j < 0 or i >= n or (j >= n) or (grid[i][j] == 0) or ((i, j) in visited):
				return False
			if grid[i][j] == 2:
				return True
			visited.add((i, j))
			x = dfs(i - 1, j)
			y = dfs(i + 1, j)
			z = dfs(i, j - 1)
			a = dfs(i, j + 1)
			return x or y or z or a
		n = len(grid)
		visited = set()
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					return dfs(i, j)


class Solution:

	def is_Possible(self, grid):
		from collections import deque
		n = len(grid)
		visited = [[False for _ in range(n)] for _ in range(n)]
		Q = deque()
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					Q.append((i, j))
					visited[i][j] = True
				if grid[i][j] == 2:
					row = i
					col = j
		while Q:
			(i, j) = Q.popleft()
			for (u, w) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
				if 0 <= i + u < n and 0 <= j + w < n:
					if not visited[i + u][j + w] and grid[i + u][j + w] != 0:
						visited[i + u][j + w] = True
						Q.append((i + u, j + w))
		if visited[row][col]:
			return 1
		return 0


class Solution:

	def is_Possible(self, G):
		from collections import deque
		Q = deque()
		n = len(G)
		for i in range(n):
			k = 0
			for j in range(n):
				if G[i][j] == 1:
					Q.append((i, j))
					k = 1
					break
			if k == 1:
				break
		while Q:
			(i, j) = Q.popleft()
			if i > 0:
				if G[i - 1][j] == 2:
					return 1
				if G[i - 1][j] == 3:
					Q.append((i - 1, j))
					G[i - 1][j] = 0
			if i < n - 1:
				if G[i + 1][j] == 2:
					return 1
				if G[i + 1][j] == 3:
					Q.append((i + 1, j))
					G[i + 1][j] = 0
			if j > 0:
				if G[i][j - 1] == 2:
					return 1
				if G[i][j - 1] == 3:
					Q.append((i, j - 1))
					G[i][j - 1] = 0
			if j < n - 1:
				if G[i][j + 1] == 2:
					return 1
				if G[i][j + 1] == 3:
					Q.append((i, j + 1))
					G[i][j + 1] = 0
		return 0


class Solution:

	def is_Possible(self, grid):
		self.nr = len(grid)
		self.nc = len(grid[0])
		r = 0
		c = 0
		fl = 0
		self.ans = 0
		for i in range(self.nr):
			for j in range(self.nc):
				if grid[i][j] == 1:
					r = i
					c = j
					fl = 1
					break
			if fl == 1:
				break
		vis = {(r, c)}
		if fl == 1:
			self.chkPth(grid, r, c, vis)
		return self.ans

	def chkPth(self, grid, i, j, vis):
		if grid[i][j] == 2:
			self.ans = 1
			return
		if self.ans == 1:
			return
		if self.chkCon(i, j + 1, grid, vis):
			vis.add((i, j + 1))
			self.chkPth(grid, i, j + 1, vis)
		if self.chkCon(i, j - 1, grid, vis):
			vis.add((i, j - 1))
			self.chkPth(grid, i, j - 1, vis)
		if self.chkCon(i - 1, j, grid, vis):
			vis.add((i - 1, j))
			self.chkPth(grid, i - 1, j, vis)
		if self.chkCon(i + 1, j, grid, vis):
			vis.add((i + 1, j))
			self.chkPth(grid, i + 1, j, vis)

	def chkCon(self, i, j, grid, vis):
		if -1 < i < self.nr and -1 < j < self.nc and ((i, j) not in vis) and (grid[i][j] == 3 or grid[i][j] == 2):
			return True
		else:
			return False


class Solution:

	def is_Possible(self, grid):
		(source, self.destination) = (None, None)
		self.grid = grid
		(self.N, self.M) = (len(grid), len(grid[0]))
		(src_find, dst_find) = (False, False)
		for i in range(self.N):
			for j in range(self.M):
				if self.grid[i][j] == 1:
					(source, src_find) = ((i, j), True)
				elif self.grid[i][j] == 2:
					(destination, dst_find) = ((i, j), True)
				if src_find and dst_find:
					break
		return self.bfs(source, destination)

	def bfs(self, source, destination):
		queue = list()
		queue.append(source)
		path = 0
		directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
		while queue:
			(x, y) = queue.pop()
			if x == destination[0] and y == destination[1]:
				return 1
			if self.grid[x][y] == 0:
				continue
			else:
				self.grid[x][y] = 0
			for dir in directions:
				dir1 = x + dir[0]
				dir2 = y + dir[1]
				if 0 <= dir1 < self.N and 0 <= dir2 < self.M:
					queue.append((dir1, dir2))
		return path


from collections import deque

class Solution:

	def is_Possible(self, grid):
		m = len(grid)
		n = len(grid[0])
		idx = 0
		idy = 0
		q = deque()
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					idx = i
					idy = j
					break
		q.append([idx, idy])
		while len(q) != 0:
			index = q.popleft()
			i = index[0]
			j = index[1]
			if grid[i][j] == 2:
				return 1
			grid[i][j] = 0
			if i + 1 < m and grid[i + 1][j] != 0:
				q.append([i + 1, j])
			if j + 1 < n and grid[i][j + 1] != 0:
				q.append([i, j + 1])
			if i - 1 >= 0 and grid[i - 1][j] != 0:
				q.append([i - 1, j])
			if j - 1 >= 0 and grid[i][j - 1] != 0:
				q.append([i, j - 1])
		return 0


class Solution:

	def is_Possible(self, grid):
		n_rows = len(grid)
		n_columns = len(grid[0])
		visited = []
		source = None
		for i in range(n_rows):
			for j in range(n_columns):
				if grid[i][j] == 1:
					source = (i, j)
					break
			if source:
				break
		pathPossible = self.dfs(grid, source, visited, n_rows, n_columns)
		return pathPossible

	def dfs(self, grid, node, visited, n_rows, n_columns):
		visited.append(node)
		(x, y) = node
		if grid[x][y] == 2:
			return True
		neighbours = self.getNeighbours(grid, node, n_rows, n_columns)
		for neighbour in neighbours:
			if neighbour not in visited:
				if self.dfs(grid, neighbour, visited, n_rows, n_columns):
					return True
		return False

	def getNeighbours(self, grid, node, n_rows, n_columns):
		(i, j) = node
		possibleNeighbours = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
		neighbours = []
		for (x, y) in possibleNeighbours:
			if 0 <= x < n_rows and 0 <= y < n_columns and (grid[x][y] != 0):
				neighbours.append((x, y))
		return neighbours


class Solution:

	def __init__(self):
		self.ans = False

	def is_Possible(self, grid):
		m = len(grid)
		n = len(grid[0])

		def dfs(x, y):
			if self.ans:
				return
			visited[x][y] = True
			if grid[x][y] == 2:
				self.ans = True
			for (i, j) in [[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]]:
				if 0 <= i < m and 0 <= j < n and grid[i][j] and (not visited[i][j]):
					dfs(i, j)
		x = None
		y = None
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					x = i
					y = j
					break
		visited = [[False] * n for i in range(m)]
		dfs(x, y)
		return self.ans


class Solution:

	def check(self, r, c, x, y, grid):
		if 0 <= x < c and 0 <= y < r:
			if grid[x][y] != 0:
				return True
		return False

	def explore(self, grid, dis_x, dis_y, pos, dest, vis):
		if pos == dest:
			return True
		if pos not in vis:
			vis.add(pos)
		for i in range(4):
			(new_x, new_y) = (pos[0] + dis_x[i], pos[1] + dis_y[i])
			if self.check(len(grid), len(grid[0]), new_x, new_y, grid):
				new_pos = tuple([new_x, new_y])
				if new_pos not in vis:
					if self.explore(grid, dis_x, dis_y, new_pos, dest, vis):
						return True
		return False

	def is_Possible(self, grid):
		dis_x = [1, -1, 0, 0]
		dis_y = [0, 0, -1, 1]
		vis = set()
		(src, dest) = (None, None)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					src = tuple([i, j])
				elif grid[i][j] == 2:
					dest = tuple([i, j])
		if self.explore(grid, dis_x, dis_y, src, dest, vis):
			return 1
		return 0


class Solution:

	def is_Possible(self, grid):
		m = len(grid)
		n = len(grid[0])
		vis = set()

		def bfs(r, c):
			if r < 0 or r == m or c < 0 or (c == n) or (grid[r][c] == 0) or ((r, c) in vis):
				return 0
			if grid[r][c] == 2:
				return 1
			vis.add((r, c))
			return bfs(r + 1, c) or bfs(r - 1, c) or bfs(r, c + 1) or bfs(r, c - 1)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					return bfs(i, j)


class Solution:

	def is_Possible(self, a):
		dist = [[float('inf') for i in range(len(a[0]))] for i in range(len(a))]
		for i in range(len(a)):
			for j in range(len(a[0])):
				if a[i][j] == 1:
					stx = i
					sty = j
				elif a[i][j] == 2:
					enx = i
					eny = j
		q = [[stx, sty]]
		dist[stx][sty] = 0
		while q:
			cur = q.pop(0)
			(x, y) = cur
			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] != 0):
					if dist[i][j] > dist[x][y] + 1:
						dist[i][j] = dist[x][y] + 1
						q.append([i, j])
		return dist[enx][eny] != float('inf')


class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		i = None
		j = None
		for u in range(n):
			for v in range(n):
				if grid[u][v] == 1:
					i = u
					j = v
					break
		if i is None:
			return 0
		vis = [[False for _ in range(n)] for _ in range(n)]

		def dfs(grid, i, j, vis):
			if not (0 <= i < n and 0 <= j < n) or vis[i][j]:
				return False
			v = grid[i][j]
			if v == 0:
				vis[i][j] = True
				return False
			if grid[i][j] == 2:
				return True
			vis[i][j] = True
			for dx in (-1, 1):
				if dfs(grid, i + dx, j, vis):
					return True
			for dy in (-1, 1):
				if dfs(grid, i, j + dy, vis):
					return True
			return False
		if dfs(grid, i, j, vis):
			return 1
		else:
			return 0


class Solution:

	def is_Possible(self, grid):
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					return self.isPath(grid, i, j, m, n)

	def isPath(self, grid, i, j, m, n):
		if i < 0 or i >= m or j < 0 or (j >= n) or (grid[i][j] == 0):
			return False
		if grid[i][j] == 2:
			return True
		grid[i][j] = 0
		ans1 = self.isPath(grid, i + 1, j, m, n)
		ans2 = self.isPath(grid, i - 1, j, m, n)
		ans3 = self.isPath(grid, i, j + 1, m, n)
		ans4 = self.isPath(grid, i, j - 1, m, n)
		return ans1 or ans2 or ans3 or ans4


class Solution:

	def is_Possible(self, grid):
		(row, col) = (len(grid), len(grid[0]))
		visited = set()

		def bfs(i, j, grid, visited):
			queue = []
			queue.append((i, j))
			visited.add((i, j))
			while queue:
				(r, c) = queue.pop(0)
				if (r + 1 >= 0 and r + 1 < row and (c >= 0) and (c < col)) and (r + 1, c) not in visited and (grid[r + 1][c] in (3, 2)):
					queue.append((r + 1, c))
					visited.add((r + 1, c))
				if (r >= 0 and r < row and (c + 1 >= 0) and (c + 1 < col)) and (r, c + 1) not in visited and (grid[r][c + 1] in (3, 2)):
					queue.append((r, c + 1))
					visited.add((r, c + 1))
				if (r - 1 >= 0 and r - 1 < row and (c >= 0) and (c < col)) and (r - 1, c) not in visited and (grid[r - 1][c] in (3, 2)):
					queue.append((r - 1, c))
					visited.add((r - 1, c))
				if (r >= 0 and r < row and (c - 1 >= 0) and (c - 1 < col)) and (r, c - 1) not in visited and (grid[r][c - 1] in (3, 2)):
					queue.append((r, c - 1))
					visited.add((r, c - 1))
			for (i, j) in visited:
				if grid[i][j] == 2:
					return 1
			return 0
		for i in range(row):
			for j in range(col):
				if (i, j) not in visited and grid[i][j] == 1:
					return bfs(i, j, grid, visited)


class Solution:

	def is_Possible(self, grid):

		def Find_Way(i, j):
			if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])):
				return False
			if grid[i][j] == 'V':
				return False
			if grid[i][j] == 0:
				return False
			if grid[i][j] == 2:
				return True
			grid[i][j] = 'V'
			return Find_Way(i - 1, j) or Find_Way(i, j - 1) or Find_Way(i + 1, j) or Find_Way(i, j + 1)
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if grid[i][j] == 1:
					return Find_Way(i, j)


class Solution:

	def is_Possible(self, grid):

		def dfs(grid, i, j):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == 0) or (grid[i][j] == '@'):
				return False
			if grid[i][j] == 2:
				return True
			if grid[i][j] == 1:
				grid[i][j] = '#'
			temp = grid[i][j]
			if grid[i][j] == 3:
				temp = grid[i][j]
				grid[i][j] = '@'
			if dfs(grid, i + 1, j):
				return True
			elif dfs(grid, i - 1, j):
				return True
			elif dfs(grid, i, j + 1):
				return True
			elif dfs(grid, i, j - 1):
				return True
			else:
				grid[i][j] = temp
				return False
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					if dfs(grid, i, j):
						return 1
					else:
						return 0


class Solution:

	def is_Possible(self, grid):
		flag = False
		visited = [[False for x in range(len(grid[0]))] for y in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and (not visited[i][j]):
					if path(grid, i, j, visited):
						flag = True
		if flag:
			return 1
		else:
			return 0

def isSafe(i, j, grid):
	if (i >= 0 and i < len(grid)) and (j >= 0 and j < len(grid)):
		return True
	else:
		return False

def path(grid, i, j, visited):
	if isSafe(i, j, grid) and (not visited[i][j]) and (grid[i][j] != 0):
		visited[i][j] = True
		if grid[i][j] == 2:
			return True
		up = path(grid, i - 1, j, visited)
		if up:
			return True
		down = path(grid, i + 1, j, visited)
		if down:
			return True
		left = path(grid, i, j - 1, visited)
		if left:
			return True
		right = path(grid, i, j + 1, visited)
		if right:
			return True
	return False


class Solution:

	def is_Possible(self, A):
		n = len(A)
		m = len(A[0])

		def bfs(A, i, j):
			q = []
			q.append((i, j))
			vis = [[False for _ in range(m)] for _ in range(n)]
			vis[i][j] = True
			while q:
				(i, j) = q.pop(0)
				posi = {(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)}
				for k in posi:
					if -1 < k[0] < n and -1 < k[1] < m and (vis[k[0]][k[1]] == False) and (A[k[0]][k[1]] != 0):
						vis[k[0]][k[1]] == True
						q.append(k)
						if A[k[0]][k[1]] == 2:
							return 1
			return 0
		for x in range(n):
			for y in range(m):
				if A[x][y] == 1:
					(i, j) = (x, y)
					break
		return bfs(A, i, j)


class Solution:

	def is_Possible(self, grid):
		(r, c) = (len(grid), len(grid[0]))
		(s, d) = ([], [])
		for i in range(r):
			for j in range(c):
				if s != [] and d != []:
					break
				if grid[i][j] == 1:
					s += [i, j]
				if grid[i][j] == 2:
					d += [i, j]
		st = [s]
		while len(st) != 0:
			(m, n) = st.pop(0)
			if m == d[0] and n == d[1]:
				return 1
			grid[m][n] = 0
			if 0 <= m + 1 < r and grid[m + 1][n] != 0:
				st.append([m + 1, n])
			if 0 <= m - 1 < r and grid[m - 1][n] != 0:
				st.append([m - 1, n])
			if 0 <= n - 1 < c and grid[m][n - 1] != 0:
				st.append([m, n - 1])
			if 0 <= n + 1 < c and grid[m][n + 1] != 0:
				st.append([m, n + 1])
		return 0


class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		src = (-1, -1)
		dest = (-1, -1)
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					src = (i, j)
				elif grid[i][j] == 2:
					dest = (i, j)
		if src == (-1, -1) or dest == (-1, -1):
			return False
		visited = [[False for j in range(n)] for i in range(n)]
		return self.checkPath(grid, visited, src[0], src[1], dest[0], dest[1])

	def checkPath(self, grid, visited, x, y, dest_x, dest_y):
		if x < 0 or y < 0 or x >= len(grid) or (y >= len(grid)) or (grid[x][y] == 0) or visited[x][y]:
			return False
		if x == dest_x and y == dest_y:
			return True
		visited[x][y] = True
		if self.checkPath(grid, visited, x - 1, y, dest_x, dest_y):
			return True
		if self.checkPath(grid, visited, x + 1, y, dest_x, dest_y):
			return True
		if self.checkPath(grid, visited, x, y - 1, dest_x, dest_y):
			return True
		if self.checkPath(grid, visited, x, y + 1, dest_x, dest_y):
			return True
		visited[x][y] = False
		return False


from collections import deque

class Solution:

	def is_Possible(self, M):
		(R, C) = (len(M), len(M[0]))
		for r in range(R):
			for c in range(C):
				if M[r][c] == 1:
					start = (r, c)
				if M[r][c] == 2:
					end = (r, c)
		q = deque([start])
		v = {start}
		while q:
			(r, c) = q.popleft()
			if (r, c) == end:
				return True
			for (nr, nc) in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
				if nr < 0 or nr == R or nc < 0 or (nc == C):
					continue
				if (nr, nc) in v:
					continue
				if M[nr][nc] == 0:
					continue
				v.add((nr, nc))
				q.append((nr, nc))
		return False


from collections import deque

class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		m = len(grid[0])
		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)]
		q = deque()
		di = 0
		dj = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					d[i][j] = 0
					c[i][j] = 'g'
					q.append((i, j))
				if grid[i][j] == 2:
					di = i
					dj = j
		while len(q) > 0:
			(i, j) = q.popleft()
			if i - 1 >= 0 and c[i - 1][j] == 'w' and (grid[i - 1][j] != 0):
				c[i - 1][j] = 'g'
				d[i - 1][j] = d[i][j] + 1
				q.append((i - 1, j))
				if grid[i - 1][j] == 2:
					break
			if i + 1 < n and c[i + 1][j] == 'w' and (grid[i + 1][j] != 0):
				c[i + 1][j] = 'g'
				d[i + 1][j] = d[i][j] + 1
				q.append((i + 1, j))
				if grid[i + 1][j] == 2:
					break
			if j - 1 >= 0 and c[i][j - 1] == 'w' and (grid[i][j - 1] != 0):
				c[i][j - 1] = 'g'
				d[i][j - 1] = d[i][j] + 1
				q.append((i, j - 1))
				if grid[i][j - 1] == 2:
					break
			if j + 1 < m and c[i][j + 1] == 'w' and (grid[i][j + 1] != 0):
				c[i][j + 1] = 'g'
				d[i][j + 1] = d[i][j] + 1
				q.append((i, j + 1))
				if grid[i][j + 1] == 2:
					break
			c[i][j] = 'b'
		if d[di][dj] == 1000000000.0:
			return 0
		return 1


class Solution:

	def is_Possible(self, grid):
		visit = set()
		dirc = [(0, -1), (-1, 0), (1, 0), (0, 1)]

		def bfs(i, j):
			que = [[i, j]]
			while que:
				for i in range(len(que)):
					x = que.pop(0)
					a = x[0]
					b = x[1]
					for (r, c) in dirc:
						s1 = r + a
						s2 = b + c
						if s1 < 0 or s2 < 0 or s1 >= len(grid) or (s2 >= len(grid[0])) or (grid[s1][s2] == 0):
							continue
						if grid[s1][s2] == 2:
							return True
						visit.add((a, b))
						if (s1, s2) not in visit:
							que.append([s1, s2])
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					if bfs(i, j):
						return True
					return False


class Solution:

	def safe(self, grid, N, x, y):
		return x >= 0 and y >= 0 and (x < N) and (y < N)

	def dfs(self, grid, N, x, y):
		visited = [[False] * N for _ in range(N)]
		stack = []
		stack.append((x, y))
		visited[x][y] = True
		Dx = [0, 0, 1, -1]
		Dy = [1, -1, 0, 0]
		while stack:
			(x, y) = stack.pop()
			for i in range(len(Dx)):
				(dx, dy) = (Dx[i], Dy[i])
				(u, v) = (x + dx, y + dy)
				if self.safe(grid, N, u, v) and (not visited[u][v]):
					if grid[u][v] == 2:
						return True
					if grid[u][v] == 3:
						stack.append((u, v))
						visited[u][v] = True
		return False

	def is_Possible(self, grid):
		N = len(grid)
		src = None
		for i in range(N):
			for j in range(N):
				if grid[i][j] == 1:
					src = (i, j)
					break
			if src:
				break
		return self.dfs(grid, N, src[0], src[1])


class Solution:

	def is_Possible(self, grid):
		(m, n) = (len(grid), len(grid[0]))

		def dfs(i, j):
			if 0 <= i < m and 0 <= j < n and (grid[i][j] == 2):
				return True
			if 0 <= i < m and 0 <= j < n and (grid[i][j] == 3):
				grid[i][j] = 0
				return dfs(i + 1, j) or dfs(i - 1, j) or dfs(i, j + 1) or dfs(i, j - 1)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					grid[i][j] = 3
					return dfs(i, j)


class Solution:

	def is_Possible(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		self.ans = 0

		def check(x, y):
			if 0 <= x < m and 0 <= y < n and (grid[x][y] == 2):
				return True
			if 0 <= x < m and 0 <= y < n and (grid[x][y] == 3):
				grid[x][y] = 0
				return True
			return False

		def bfs(i, j):
			if grid[i][j] == 2:
				self.ans = 1
				return
			if check(i + 1, j):
				bfs(i + 1, j)
			if check(i, j + 1):
				bfs(i, j + 1)
			if check(i - 1, j):
				bfs(i - 1, j)
			if check(i, j - 1):
				bfs(i, j - 1)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					bfs(i, j)
					return self.ans


class Solution:

	def dfs(self, row, column, grid, visited, res):
		if row > len(grid) or column > len(grid[0]):
			return
		if res[0] == True:
			return
		visited[row][column] = True
		if grid[row][column] == 2:
			res[0] = True
			return
		if row + 1 < len(grid) and visited[row + 1][column] == False and (grid[row + 1][column] != 0):
			self.dfs(row + 1, column, grid, visited, res)
		if row - 1 >= 0 and visited[row - 1][column] == False and (grid[row - 1][column] != 0):
			self.dfs(row - 1, column, grid, visited, res)
		if column + 1 < len(grid[0]) and visited[row][column + 1] == False and (grid[row][column + 1] != 0):
			self.dfs(row, column + 1, grid, visited, res)
		if column - 1 >= 0 and visited[row][column - 1] == False and (grid[row][column - 1] != 0):
			self.dfs(row, column - 1, grid, visited, res)

	def is_Possible(self, grid):
		row = 100
		column = 100
		res = [False]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					row = i
					column = j
					break
		visited = [[False for i in range(len(grid[0]))] for j in range(len(grid))]
		self.dfs(row, column, grid, visited, res)
		return res[0]


class Solution:

	def is_Possible(self, grid):
		(m, n) = (len(grid), len(grid[0]))
		visited = [[False for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					source = [i, j]
				elif grid[i][j] == 2:
					destination = [i, j]
		return self.dfs(source, destination, grid, visited)

	def dfs(self, source, destination, grid, visited):
		(m, n) = (len(grid), len(grid[0]))
		(source_i, source_j) = source
		visited[source_i][source_j] = True
		if grid[source_i][source_j] == 0:
			return False
		(destination_i, destination_j) = destination
		if source_i == destination_i and source_j == destination_j:
			return True
		possible = False
		if source_i - 1 >= 0 and (not visited[source_i - 1][source_j]) and self.dfs([source_i - 1, source_j], destination, grid, visited):
			return True
		if source_i + 1 < m and (not visited[source_i + 1][source_j]) and self.dfs([source_i + 1, source_j], destination, grid, visited):
			return True
		if source_j - 1 >= 0 and (not visited[source_i][source_j - 1]) and self.dfs([source_i, source_j - 1], destination, grid, visited):
			return True
		if source_j + 1 < n and (not visited[source_i][source_j + 1]) and self.dfs([source_i, source_j + 1], destination, grid, visited):
			return True
		return False


class Solution:

	def is_Possible(self, grid):
		visited = [[0] * len(grid[0])] * len(grid)
		q = []
		(start, end) = self.posfind(grid)
		visited[start[0]][start[1]] = 1
		q.append(start)
		while len(q) != 0:
			(i, j) = q.pop(0)
			for (r, c) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
				if self.isValid([r, c], grid):
					if grid[r][c] == 3:
						q.append([r, c])
					if grid[r][c] == 2:
						return 1
		return 0

	def isValid(self, pos, grid):
		x = pos[0]
		y = pos[1]
		if 0 <= x < len(grid) and 0 <= y < len(grid[0]):
			return True
		else:
			return False

	def bfs(self, i, grid, start, end, visited):
		pass

	def posfind(self, grid):
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if grid[i][j] == 1:
					start = [i, j]
				elif grid[i][j] == 2:
					end = [i, j]
		return (start, end)


class Solution:

	def dfs(self, grid, visited, current):
		(i, j) = current
		if current in visited or i < 0 or i >= len(grid) or (j < 0) or (j >= len(grid[0])) or (grid[i][j] == 0):
			return False
		elif grid[i][j] == 2:
			return True
		elif grid[i][j] == 3:
			visited.append(current)
		down = self.dfs(grid, visited, [i - 1, j])
		up = self.dfs(grid, visited, [i + 1, j])
		right = self.dfs(grid, visited, [i, j + 1])
		left = self.dfs(grid, visited, [i, j - 1])
		return left or right or up or down

	def is_Possible(self, grid):
		source = [0, 0]
		destination = [0, 0]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					source = [i, j]
					break
		visited = list()
		current = source
		if self.dfs(grid, visited, current):
			return 1
		return 0


class Solution:

	def is_Possible(self, grid):
		(ROW, COL) = (len(grid), len(grid[0]))
		visited = set()
		(source, destination) = ([], [])
		for i in range(ROW):
			for j in range(COL):
				if grid[i][j] == 1:
					source = [i, j]
				if grid[i][j] == 2:
					destination = [i, j]

		def findPath(r, c):
			if r < 0 or c < 0 or r >= ROW or (c >= COL):
				return False
			if (r, c) in visited:
				return False
			if grid[r][c] == 0:
				return False
			if [r, c] == destination:
				return True
			visited.add((r, c))
			if findPath(r + 1, c) or findPath(r - 1, c) or findPath(r, c + 1) or findPath(r, c - 1):
				return True
			return False
		return findPath(source[0], source[1])


import collections

class Solution:

	def is_Possible(self, grid):
		di = [0, -1, 0, 1]
		dj = [1, 0, -1, 0]
		q = collections.deque([])
		visited = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					q.append((i, j))
					visited.add((i, j))
		while q:
			(i, j) = q.popleft()
			if grid[i][j] == 2:
				return True
			for d in range(4):
				newi = i + di[d]
				newj = j + dj[d]
				if not (0 <= newi < len(grid) and 0 <= newj < len(grid[0])):
					continue
				if (newi, newj) in visited or grid[newi][newj] == 0:
					continue
				q.append((newi, newj))
				visited.add((newi, newj))
		return False


from collections import deque

class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					source = (i, j)
				elif grid[i][j] == 2:
					dest = (i, j)
		visited = [[False for _ in range(n)] for _ in range(n)]
		q = deque()
		q.append(source)
		visited[source[0]][source[1]] = True
		while q:
			curr = q.popleft()
			if curr == dest:
				return True
			(row, col) = (curr[0], curr[1])
			neighbors = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
			for nei in neighbors:
				(nrow, ncol) = (nei[0], nei[1])
				if 0 <= nrow < n and 0 <= ncol < n and (not visited[nrow][ncol]) and (grid[nrow][ncol] != 0):
					q.append(nei)
					visited[nrow][ncol] = True
		return False


class Solution:

	def is_Possible(self, grid):
		src = None
		N = len(grid)
		for i in range(N):
			if 1 in grid[i]:
				src = [i, grid[i].index(1)]
				break
		q = []
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		q.append(src)
		while q:
			it = q.pop(0)
			r = it[0]
			c = it[1]
			for i in range(4):
				newr = r + dr[i]
				newc = c + dc[i]
				if 0 <= newr < N and 0 <= newc < N and (grid[newr][newc] == 2):
					return 1
				elif 0 <= newr < N and 0 <= newc < N and (grid[newr][newc] == 3):
					q.append([newr, newc])
		return 0


class Solution:

	def is_Possible(self, grid):
		r_n = len(grid)
		if r_n == 0:
			return False
		c_n = len(grid[0])
		sou = []
		des = []
		for i in range(r_n):
			for j in range(c_n):
				if grid[i][j] == 1:
					sou = [i, j]
				elif grid[i][j] == 2:
					des = [i, j]
				if sou and des:
					break
		visited = set()

		def dfs(cur_loc):
			if cur_loc[0] < 0 or cur_loc[0] >= r_n or cur_loc[1] < 0 or (cur_loc[1] >= c_n) or (grid[cur_loc[0]][cur_loc[1]] == 0) or ((cur_loc[0], cur_loc[1]) in visited):
				return False
			visited.add((cur_loc[0], cur_loc[1]))
			if grid[cur_loc[0]][cur_loc[1]] == 2:
				return True
			return dfs([cur_loc[0] - 1, cur_loc[1]]) or dfs([cur_loc[0] + 1, cur_loc[1]]) or dfs([cur_loc[0], cur_loc[1] - 1]) or dfs([cur_loc[0], cur_loc[1] + 1])
		return dfs(sou)


class Solution:

	def is_Possible(self, grid):
		r = len(grid)
		c = len(grid[0])
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 1:
					return self.dfs(grid, i, j, r, c)
		return False

	def dfs(self, grid, i, j, r, c):
		if i < 0 or j < 0 or i >= r or (j >= c) or (grid[i][j] == 0) or (grid[i][j] == -1):
			return False
		if grid[i][j] == 2:
			return True
		if grid[i][j] == 3:
			grid[i][j] = -1
		l = self.dfs(grid, i - 1, j, r, c)
		ri = self.dfs(grid, i, j - 1, r, c)
		t = self.dfs(grid, i + 1, j, r, c)
		d = self.dfs(grid, i, j + 1, r, c)
		return l or ri or t or d


class Solution:

	def is_Possible(self, grid):
		n = len(grid)

		def checker(i, j):
			if i < 0 and j < 0 or i >= n or j >= n or (grid[i][j] == 0):
				return True
			return False

		def dfs(i, j):
			if checker(i, j):
				return False
			if grid[i][j] == 2:
				return True
			grid[i][j] = 0
			path = [(1, 0), (-1, 0), (0, 1), (0, -1)]
			for t in range(4):
				newx = i + path[t][0]
				newy = j + path[t][1]
				if dfs(newx, newy):
					return True
			return False
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					return dfs(i, j)
		return False


class Solution:

	def dfs(self, src, visited, grid, n):
		row = src[0]
		col = src[1]
		if row < n and col < n and (row >= 0) and (col >= 0) and (visited[row][col] == 0):
			visited[row][col] = 1
			if grid[row][col] == 2:
				return True
			if grid[row][col] == 3:
				return self.dfs([row + 1, col], visited, grid, n) or self.dfs([row - 1, col], visited, grid, n) or self.dfs([row, col - 1], visited, grid, n) or self.dfs([row, col + 1], visited, grid, n)

	def is_Possible(self, grid):
		src = None
		n = len(grid)
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					grid[i][j] = 3
					src = [i, j]
					break
		visited = [[0 for i in range(n)] for j in range(n)]
		return self.dfs(src, visited, grid, n)


class Solution:

	def is_Possible(self, grid):

		def DFS(row, col, n, grid, visited):
			if row < 0 or col < 0 or row >= n or (col >= n) or (grid[row][col] == 0) or (visited[row][col] == True):
				return False
			if grid[row][col] == 2:
				return True
			visited[row][col] = True
			v1 = DFS(row + 1, col, n, grid, visited)
			v2 = DFS(row, col + 1, n, grid, visited)
			v3 = DFS(row - 1, col, n, grid, visited)
			v4 = DFS(row, col - 1, n, grid, visited)
			return v1 or v2 or v3 or v4
		visited = [[False] * n for i in range(n)]
		row = col = None
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					row = i
					col = j
					break
		ans = DFS(row, col, n, grid, visited)
		return ans


class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		(u, v) = (0, 0)
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					(u, v) = (i, j)
					break
		visited = [[False for _ in range(n)] for _ in range(n)]

		def dfs(i, j, grid, visited):
			if not (0 <= i < n and 0 <= j < n) or visited[i][j]:
				return False
			if grid[i][j] == 0:
				visited[i][j] = True
				return False
			if grid[i][j] == 2:
				return True
			visited[i][j] = True
			for x in (-1, 1):
				if dfs(i + x, j, grid, visited):
					return True
			for y in (-1, 1):
				if dfs(i, j + y, grid, visited):
					return True
			return False
		if dfs(u, v, grid, visited):
			return 1
		else:
			return 0


class Solution:

	def is_Possible(self, grid):
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					visited = set()
					return self.dfs(grid, i, j, visited)

	def dfs(self, grid, sx, sy, visited):
		if sx < 0 or sy < 0 or sx >= len(grid) or (sy >= len(grid[0])) or ((sx, sy) in visited) or (grid[sx][sy] == 0):
			return False
		if grid[sx][sy] == 2:
			return True
		visited.add((sx, sy))
		for (x, y) in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
			nr = sx + x
			nc = sy + y
			if self.dfs(grid, nr, nc, visited):
				return True
		return False


class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		m = len(grid[0])
		stack = []
		for i in range(n):
			if 1 in grid[i]:
				stack.append((i, grid[i].index(1)))
				break
		while stack:
			(i, j) = stack.pop()
			if grid[i][j] == 2:
				return True
			grid[i][j] = 0
			if i > 0 and grid[i - 1][j]:
				stack.append((i - 1, j))
			if i < n - 1 and grid[i + 1][j]:
				stack.append((i + 1, j))
			if j > 0 and grid[i][j - 1]:
				stack.append((i, j - 1))
			if j < m - 1 and grid[i][j + 1]:
				stack.append((i, j + 1))
		return False


from collections import deque

class Solution:

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

	def is_Possible(self, grid):
		q = deque()
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					q.append((i, j))
					break
		r = [1, 0, 0, -1]
		c = [0, 1, -1, 0]
		while q:
			(x, y) = q.popleft()
			for i in range(4):
				if self.isValid(x + r[i], y + c[i], m, n):
					if grid[x + r[i]][y + c[i]] == 2:
						return True
					elif grid[x + r[i]][y + c[i]] == 3:
						grid[x + r[i]][y + c[i]] == 1
						q.append((x + r[i], y + c[i]))
		return False


class Solution:

	def is_Possible(self, grid):

		def dfs(row, col, rows, cols, seen, endx, endy):
			if row < 0 or row >= rows or col < 0 or (col >= cols):
				return False
			if (row, col) in seen:
				return False
			if grid[row][col] == 0:
				return False
			if row == endx and col == endy:
				return True
			seen.add((row, col))
			return dfs(row + 1, col, rows, cols, seen, endx, endy) or dfs(row - 1, col, rows, cols, seen, endx, endy) or dfs(row, col - 1, rows, cols, seen, endx, endy) or dfs(row, col + 1, rows, cols, seen, endx, endy)
		(rows, cols) = (len(grid), len(grid[0]))
		startx = starty = -1
		endx = endy = -1
		for x in range(rows):
			for y in range(cols):
				if grid[x][y] == 1:
					(startx, starty) = (x, y)
				elif grid[x][y] == 2:
					(endx, endy) = (x, y)
		if dfs(startx, starty, rows, cols, set(), endx, endy):
			return 1
		return 0


from collections import deque

class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		visited = [[0] * n for _ in range(n)]
		dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		src = [-1, -1]
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					(src[0], src[1]) = (i, j)
					break
		que = deque([src])
		while que:
			(i, j) = que.popleft()
			visited[i][j] = 1
			if grid[i][j] == 2:
				return 1
			for (delRow, delCol) in dirc:
				nr = delRow + i
				nc = delCol + j
				if nr >= 0 and nr < n and (nc >= 0) and (nc < n) and (grid[nr][nc] != 0) and (not visited[nr][nc]):
					que.append((nr, nc))
		return 0


class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		visited = [[0] * n for _ in range(n)]
		dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]

		def detect(i, j):
			visited[i][j] = 1
			if grid[i][j] == 2:
				return 1
			for (delRow, delCol) in dirc:
				nr = delRow + i
				nc = delCol + j
				if nr >= 0 and nr < n and (nc >= 0) and (nc < n) and (grid[nr][nc] != 0) and (not visited[nr][nc]):
					if detect(nr, nc):
						return 1
			return 0
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					return detect(i, j)
		return 0


from collections import deque

class Solution:

	def is_Possible(self, matrix):
		n = len(grid)
		source = None
		dest = None
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					source = (i, j)
				elif grid[i][j] == 2:
					dest = (i, j)
		visited = [[False for _ in range(n)] for _ in range(n)]
		if not source or not dest:
			return 0
		queue = deque()
		queue.append(source)
		visited[source[0]][source[1]] = True
		while queue:
			cur_pos = queue.popleft()
			if cur_pos == dest:
				return 1
			for move in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				next_pos = (cur_pos[0] + move[0], cur_pos[1] + move[1])
				if 0 <= next_pos[0] < n and 0 <= next_pos[1] < n and (grid[next_pos[0]][next_pos[1]] != 0) and (not visited[next_pos[0]][next_pos[1]]):
					visited[next_pos[0]][next_pos[1]] = True
					queue.append(next_pos)
		return 0


from collections import deque

class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		m = len(grid[0])
		rl = [-1, 1, 0, 0]
		cl = [0, 0, -1, 1]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					grid[i][j] = 0
					q = deque()
					q.append([i, j])
					while len(q) > 0:
						temp = q.popleft()
						r = temp[0]
						c = temp[1]
						for k in range(4):
							nrow = r + rl[k]
							ncol = c + cl[k]
							if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m):
								if grid[nrow][ncol] == 2:
									return 1
								elif grid[nrow][ncol] == 3:
									grid[nrow][ncol] = 0
									q.append([nrow, ncol])
					break
		return 0


from collections import deque

class Solution:

	def is_Possible(self, grid):
		N = len(grid)

		def getSourceDest():
			source = dest = None
			for i in range(N):
				for j in range(N):
					if grid[i][j] == 1:
						source = (i, j)
					elif grid[i][j] == 2:
						dest = (i, j)
					if source and dest:
						return [source, dest]
			return [None, None]
		(source, dest) = getSourceDest()
		if not source:
			return -1
		grid[source[0]][source[1]] = 0
		grid[dest[0]][dest[1]] = 3
		dq = deque([source])
		while dq:
			(r, c) = dq.popleft()
			if (r, c) == dest:
				return 1
			for (dr, dc) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
				(nr, nc) = (r + dr, c + dc)
				if 0 <= nr < N and 0 <= nc < N and (grid[nr][nc] == 3):
					grid[r][c] = 0
					dq.append((nr, nc))
		return 0


class Solution:

	def is_Possible(self, grid):
		if self.is_path(grid):
			return 1
		return 0

	def check_path(self, visited, grid, i, j):
		if self.is_safe(grid, i, j) and (not visited[i][j]) and grid[i][j]:
			visited[i][j] = True
			if grid[i][j] == 2:
				return True
			up = self.check_path(visited, grid, i - 1, j)
			if up:
				return True
			down = self.check_path(visited, grid, i + 1, j)
			if down:
				return True
			left = self.check_path(visited, grid, i, j - 1)
			if left:
				return True
			right = self.check_path(visited, grid, i, j + 1)
			if right:
				return True
		return False

	def is_safe(self, grid, i, j):
		if i < len(grid) and i >= 0 and (j >= 0) and (j < len(grid[0])):
			return True
		else:
			return False

	def is_path(self, grid):
		visited = [[False for x in range(len(grid))] for _ in range(len(grid[0]))]
		flag = False
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and (not visited[i][j]):
					if self.check_path(visited, grid, i, j):
						flag = True
						break
		return flag


from collections import deque

def isvalid(x, y, n, m):
	if x >= 0 and x < n and (y >= 0) and (y < m):
		return True
	return False

class Solution:

	def is_Possible(self, grid):
		N = len(grid)
		M = len(grid[0])
		q = deque()
		for i in range(N):
			for j in range(M):
				if grid[i][j] == 1:
					q.append([i, j])
					break
		dx = [0, 0, -1, 1]
		dy = [-1, 1, 0, 0]
		while q:
			(x, y) = q.popleft()
			for i in range(4):
				nx = dx[i] + x
				ny = dy[i] + y
				if isvalid(nx, ny, N, M):
					if grid[nx][ny] == 2:
						return True
					elif grid[nx][ny] == 3:
						grid[nx][ny] = 1
						q.append([nx, ny])
		return False


class Solution:

	def is_Possible(self, grid):

		def canFindDestination(i, j):
			if i < 0 or j < 0 or i == len(grid) or (j == len(grid[0])) or (grid[i][j] == 0):
				return False
			if grid[i][j] == 2:
				return True
			grid[i][j] = 0
			found = False
			for k in range(-1, 2, 2):
				found = found or canFindDestination(i + k, j) or canFindDestination(i, j + k)
				if found:
					return True
			return found
		for i in range(0, len(grid)):
			for j in range(0, len(grid[0])):
				if grid[i][j] == 1:
					if canFindDestination(i, j):
						return True
					return False


class Solution:

	def is_Possible(self, grid):
		source = None
		destination = None
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 2:
					destination = (i, j)
				if grid[i][j] == 1:
					source = (i, j)
		queue = [source]
		visited = [source]
		while queue:
			x = queue.pop(0)
			x1 = x[0]
			x2 = x[1]
			if x1 - 1 >= 0:
				if grid[x1 - 1][x2] == 3 and (x1 - 1, x2) not in visited:
					queue.append((x1 - 1, x2))
					visited.append((x1 - 1, x2))
				elif grid[x1 - 1][x2] == 2:
					return True
			if x1 + 1 < m:
				if grid[x1 + 1][x2] == 3 and (x1 + 1, x2) not in visited:
					queue.append((x1 + 1, x2))
					visited.append((x1 + 1, x2))
				elif grid[x1 + 1][x2] == 2:
					return True
			if x2 - 1 >= 0:
				if grid[x1][x2 - 1] == 3 and (x1, x2 - 1) not in visited:
					queue.append((x1, x2 - 1))
					visited.append((x1, x2 - 1))
				elif grid[x1][x2 - 1] == 2:
					return True
			if x2 + 1 < n:
				if grid[x1][x2 + 1] == 3 and (x1, x2 + 1) not in visited:
					queue.append((x1, x2 + 1))
					visited.append((x1, x2 + 1))
				elif grid[x1][x2 + 1] == 2:
					return True
		return False


import queue

def is_valid(x, y, grid, n):
	if x < 0 or y < 0 or x >= n or (y >= n):
		return False
	if grid[x][y] == 0:
		return False
	return True

def bfs(grid):
	stack = queue.Queue()
	(n, m) = (len(grid), len(grid[0]))
	(source, target) = (None, None)
	for i in range(n):
		for j in range(m):
			if grid[i][j] == 1:
				source = (i, j)
			elif grid[i][j] == 2:
				target = (i, j)
	stack.put(source)
	visited = set()
	visited.add(source)
	while not stack.empty():
		top = stack.get()
		if top == target:
			return True
		for (i, j) in zip([0, 0, 1, -1], [1, -1, 0, 0]):
			(ti, tj) = (top[0] + i, top[1] + j)
			if (ti, tj) not in visited and is_valid(ti, tj, grid, n):
				stack.put((ti, tj))
				visited.add((ti, tj))
	return False

class Solution:

	def is_Possible(self, grid):
		return bfs(grid)


from collections import deque

class Solution:

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

	def is_Possible(self, grid):
		n = len(grid)
		visited = [[False for _ in range(n)] for _ in range(n)]
		sx = 0
		sy = 0
		dx = 0
		dy = 0
		moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					sx = i
					sy = j
					break
		x = deque()
		y = deque()
		visited[sx][sy] = True
		x.append(sx)
		y.append(sy)
		while len(x) > 0:
			fx = x.popleft()
			fy = y.popleft()
			for move in moves:
				nx = fx + move[0]
				ny = fy + move[1]
				if not self.isValid(nx, ny, n):
					continue
				if visited[nx][ny]:
					continue
				if grid[nx][ny] == 3:
					x.append(nx)
					y.append(ny)
					visited[nx][ny] = True
				if grid[nx][ny] == 2:
					return True
		return False


class Solution:

	def is_Possible(self, grid):
		n = len(grid)
		visited = [[False for i in range(n)] for j in range(n)]
		for i in range(n):
			for j in range(n):
				if grid[i][j] == 1:
					(start_x, start_y) = (i, j)
				elif not grid[i][j]:
					visited[i][j] = True
		return self.dfs(start_x, start_y, n, grid, visited)

	def dfs(self, i, j, n, grid, visited):
		if not (i >= 0 and i < n and (j >= 0) and (j < n)) or visited[i][j]:
			return False
		if grid[i][j] == 2:
			return True
		visited[i][j] = True
		return self.dfs(i + 1, j, n, grid, visited) or self.dfs(i - 1, j, n, grid, visited) or self.dfs(i, j + 1, n, grid, visited) or self.dfs(i, j - 1, n, grid, visited)


class Solution:

	def is_Possible(self, grid):
		m = len(grid)
		n = len(grid[0])
		visited = [[False for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 0:
					visited[i][j] = True
				elif grid[i][j] == 1:
					source = [i, j]
				elif grid[i][j] == 2:
					des = [i, j]
		q = [source]
		p = 0
		arr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		while p < len(q):
			node = q[p]
			if node == des:
				return True
			for i in arr:
				a = node[0] + i[0]
				b = node[1] + i[1]
				if a >= 0 and a < m and (b >= 0) and (b < n) and (visited[a][b] != True):
					q.append([a, b])
					visited[a][b] = True
			p += 1
		return False