Given a N x M grid. Find All possible paths from top left to bottom right.From each cell you can either move only to right or down.
Example 1:
Input: 1 2 3
       4 5 6
Output: 1 4 5 6
        1 2 5 6 
        1 2 3 6
Explanation: We can see that there are 3 
paths from the cell (0,0) to (1,2).
Example 2:
Input: 1 2
       3 4
Output: 1 2 4
        1 3 4
Your Task:
You don't need to read input or print anything. Your task is to complete the function findAllPossiblePaths() which takes two integers n,m and grid[][]  as input parameters and returns all possible paths from the top left cell to bottom right cell in a 2d array.
Expected Time Complexity: O(2^N*M)
Expected Auxiliary Space: O(N)
Constraints:
1 <= n,m <= 10^{ }
1 <= grid[i][j] <= n*m
n * m < 20

Source: geeksforgeeks | Difficulty: EASY
Tags: Matrices

Data structures

Complete search

Starter code: 

from typing import List

class Solution:

    def findAllPossiblePaths(self, n : int, m : int, grid : List[List[int]]) -> List[List[int]]:

        # code here

        



Solutions:
from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		self.m = m
		self.n = n
		self.grid = grid
		self.l = []
		temp = [0] * (m + n - 1)
		temp[0] = grid[0][0]
		temp[-1] = grid[-1][-1]
		self.recur(temp, 1, 0, 0)
		return self.l

	def recur(self, temp, inx, i, j):
		if i + 1 < self.n and j < self.m:
			temp[inx] = self.grid[i + 1][j]
			self.recur(temp, inx + 1, i + 1, j)
		if i < self.n and j + 1 < self.m:
			temp[inx] = grid[i][j + 1]
			self.recur(temp, inx + 1, i, j + 1)
		if i == self.n - 1 and j == self.m - 1:
			self.l.append(temp.copy())
			return


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		res = []

		def sol(r, c, n, m, grid, arr):
			if r >= n or c >= m:
				return
			if r == n - 1 and c == m - 1:
				res.append(arr.copy())
				return
			sol(r + 1, c, n, m, grid, arr + [grid[r][c]])
			sol(r, c + 1, n, m, grid, arr + [grid[r][c]])
		sol(0, 0, n, m, grid, [])
		for i in range(len(res)):
			res[i].append(grid[n - 1][m - 1])
		return res


from typing import List

class Solution:

	def findPaths(self, row, col, n, m, ans, paths, grid):
		if row >= n or col >= m:
			return
		paths.append(grid[row][col])
		if row == n - 1 and col == m - 1:
			ans.append(paths[:])
		self.findPaths(row + 1, col, n, m, ans, paths, grid)
		self.findPaths(row, col + 1, n, m, ans, paths, grid)
		paths.pop()

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		paths = []
		self.findPaths(0, 0, n, m, ans, paths, grid)
		return ans


from typing import List

class Solution:

	def calculate(self, n, m, i, j, ans, temp, grid):
		if i >= n or j >= m:
			return
		temp.append(grid[i][j])
		if i == n - 1 and j == m - 1:
			ans.append(temp[:])
		self.calculate(n, m, i + 1, j, ans, temp, grid)
		self.calculate(n, m, i, j + 1, ans, temp, grid)
		temp.pop()

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		temp = []
		self.calculate(n, m, 0, 0, ans, temp, grid)
		return ans


def func(pos, a, temp, visted, ans):
	(x, y) = pos
	if 0 <= x < len(a) and 0 <= y < len(a[0]) and ((x, y) not in visted):
		visted.add((x, y))
		if x == len(a) - 1 and y == len(a[0]) - 1:
			ans.append(temp[:] + [a[x][y]])
		func((x + 1, y), a, temp + [a[x][y]], visted, ans)
		func((x, y + 1), a, temp + [a[x][y]], visted, ans)
		visted.remove((x, y))
from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, a: List[List[int]]) -> List[List[int]]:
		visted = set()
		ans = []
		func((0, 0), a, [], visted, ans)
		return ans


from typing import List

def rec(mat, i, j, res, ans):
	if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])):
		return
	if i == len(mat) - 1 and j == len(mat[0]) - 1:
		res.append(mat[i][j])
		ans.append(res[:])
		res.pop()
		return
	res.append(mat[i][j])
	rec(mat, i + 1, j, res, ans)
	rec(mat, i, j + 1, res, ans)
	res.pop()

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		rec(grid, 0, 0, [], ans)
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, arr: List[List[int]]) -> List[List[int]]:
		vis = [[0 for i in range(m)] for j in range(n)]
		ans = []
		fin = []

		def safe(newi, newj, vis, ans, arr, n, m):
			if (newi >= 0 and newi < n) and (newj < m and newj >= 0) and (vis[newi][newj] != 1):
				return True
			else:
				return False

		def solve(i, j, arr, vis, ans, fin, n, m):
			if i == n - 1 and j == m - 1:
				ans += [arr[i][j]]
				fin.append(ans)
				return
			if safe(i + 1, j, vis, ans, arr, n, m):
				vis[i][j] = 1
				solve(i + 1, j, arr, vis, ans + [arr[i][j]], fin, n, m)
				vis[i][j] = 0
			if safe(i, j + 1, vis, ans, arr, n, m):
				vis[i][j] = 1
				solve(i, j + 1, arr, vis, ans + [arr[i][j]], fin, n, m)
				vis[i][j] = 0
		solve(0, 0, arr, vis, ans, fin, n, m)
		return fin


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		(ans, r, i, j) = ([], [], 0, 0)

		def dfs(i, j, n, m):
			if i >= n or j >= m:
				return
			if i == n - 1 and j == m - 1:
				r.append(grid[i][j])
				ans.append(r.copy())
				r.pop()
				return
			r.append(grid[i][j])
			dfs(i + 1, j, n, m)
			dfs(i, j + 1, n, m)
			r.pop()
		dfs(i, j, n, m)
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		di = [1, 0]
		dj = [0, 1]

		def helper(i, j, grid, ans, vis, move):
			if i == n - 1 and j == m - 1:
				move.append(grid[i][j])
				ans.append(move.copy())
				move.pop()
				return
			for index in range(2):
				nexti = i + di[index]
				nextj = j + dj[index]
				if nexti >= 0 and nextj >= 0 and (nexti < n) and (nextj < m) and (vis[nexti][nextj] == False):
					vis[i][j] = True
					move.append(grid[i][j])
					helper(nexti, nextj, grid, ans, vis, move)
					vis[i][j] = False
					move.pop()
		vis = [[False] * m for i in range(n)]
		ans = []
		helper(0, 0, grid, ans, vis, [])
		return ans


from typing import List

def mati(n, m, row, col, mat, ans, res):
	if row == n - 1 and col == m - 1:
		ans.append(mat[row][col])
		res.append(ans)
		return
	if n <= row or m <= col:
		return
	ans.append(mat[row][col])
	mati(n, m, row + 1, col, mat, ans.copy(), res)
	mati(n, m, row, col + 1, mat, ans.copy(), res)

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		res = []
		mati(n, m, 0, 0, grid, ans, res)
		return res


from typing import List

class Solution:

	def paths(self, i, j, n, m, grid, curr, ans):
		if i < 0 or i >= n or j < 0 or (j >= m):
			return
		if i == n - 1 and j == m - 1:
			curr.append(grid[i][j])
			ans.append(curr)
			return
		self.paths(i + 1, j, n, m, grid, curr + [grid[i][j]], ans)
		self.paths(i, j + 1, n, m, grid, curr + [grid[i][j]], ans)

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		self.paths(0, 0, n, m, grid, [], ans)
		return ans


from itertools import permutations
from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		return sorted(self.helper((0, 0), grid, n - 1, m - 1, []), reverse=True)

	def helper(self, pos, grid, n, m, path1):
		path2 = path1.copy()
		path2.append(grid[pos[0]][pos[1]])
		if pos == (n, m):
			return [path2]
		down = []
		if pos[0] < n:
			down = self.helper((pos[0] + 1, pos[1]), grid, n, m, path2)
		right = []
		if pos[1] < m:
			right = self.helper((pos[0], pos[1] + 1), grid, n, m, path2)
		return down + right


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		res = []

		def backtrack(x, y, path):
			if x == n - 1 and y == m - 1:
				res.append([grid[i][j] for (i, j) in path])
			if x + 1 < n:
				backtrack(x + 1, y, path + [(x + 1, y)])
			if y + 1 < m:
				backtrack(x, y + 1, path + [(x, y + 1)])
		backtrack(0, 0, [(0, 0)])
		return res


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		global a
		a = []

		def sol(i, j, grid, p):
			global a
			if i < 0 or j < 0 or i >= n or (j >= m):
				return
			if i == n - 1 and j == m - 1:
				a.append(p + [grid[i][j]])
				return
			sol(i + 1, j, grid, p + [grid[i][j]])
			sol(i, j + 1, grid, p + [grid[i][j]])
		sol(0, 0, grid, [])
		return a


from typing import List

def util(grid, r, c, tr, tc, path, ans):
	if r > tr or c > tc:
		return
	if r == tr and c == tc:
		ans.append([x for x in path] + [grid[r][c]])
	path.append(grid[r][c])
	util(grid, r + 1, c, tr, tc, path, ans)
	util(grid, r, c + 1, tr, tc, path, ans)
	path.pop()

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		util(grid, 0, 0, n - 1, m - 1, [], ans)
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:

		def recsol(temp, ans, row, col):
			if row == n - 1 and col == m - 1:
				temp.append(grid[row][col])
				ans.append(temp[:])
				temp.pop()
				return
			if row < n and col < m:
				temp.append(grid[row][col])
				recsol(temp, ans, row + 1, col)
				recsol(temp, ans, row, col + 1)
				temp.pop()
			return ans
		k = recsol([], [], 0, 0)
		return k


from typing import List

class Solution:

	def helper(self, x, y, row, col, path):
		if (x, y) == (row - 1, col - 1):
			self.path.append(path[:] + [grid[x][y]])
			return
		if -1 < x + 1 < row:
			self.helper(x + 1, y, row, col, path + [grid[x][y]])
		if -1 < y + 1 < col:
			self.helper(x, y + 1, row, col, path + [grid[x][y]])

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		self.path = []
		self.helper(0, 0, n, m, [])
		return self.path


from typing import List
v = []

def traverse(grid, row, col, z):
	if row == len(grid) - 1 and col == len(grid[0]) - 1:
		v.append(z + [grid[row][col]])
	elif row == len(grid) - 1:
		traverse(grid, row, col + 1, z + [grid[row][col]])
	elif col == len(grid[0]) - 1:
		traverse(grid, row + 1, col, z + [grid[row][col]])
	else:
		traverse(grid, row + 1, col, z + [grid[row][col]])
		traverse(grid, row, col + 1, z + [grid[row][col]])

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		global v
		v = []
		traverse(grid, 0, 0, [])
		return v


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		self.ans = []
		self.helper(0, 0, grid, [], self.ans)
		return self.ans

	def helper(self, r, c, l, temp, ans):
		if r == len(l) or c == len(l[0]) or r < 0 or (c < 0):
			return
		if r == len(l) - 1 and c == len(l[0]) - 1:
			temp.append(l[r][c])
			self.ans.append(temp.copy())
			temp.pop()
			return
		temp.append(l[r][c])
		self.helper(r + 1, c, l, temp, self.ans)
		self.helper(r, c + 1, l, temp, self.ans)
		temp.pop()


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:

		def backtrack(row, col, temp):
			if row >= n or col >= m:
				return
			temp.append(grid[row][col])
			if row == n - 1 and col == m - 1:
				ans.append(temp.copy())
			backtrack(row + 1, col, temp.copy())
			backtrack(row, col + 1, temp.copy())
		ans = []
		backtrack(0, 0, [])
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, R, C, M):
		ans = []
		rec(0, 0, R, C, M, [], ans)
		return ans

def rec(r, c, R, C, M, acc, ans):
	if r == R or c == C:
		return
	acc.append(M[r][c])
	if (r, c) == (R - 1, C - 1):
		ans.append(acc[:])
	rec(r + 1, c, R, C, M, acc, ans)
	rec(r, c + 1, R, C, M, acc, ans)
	acc.pop()


from typing import List

class Solution:

	def findAllPossiblePaths(self, R, C, M):
		ans = []
		rec(0, 0, R, C, M, set(), [], ans)
		return ans

def rec(r, c, R, C, M, v, acc, ans):
	if (r, c) == (R - 1, C - 1):
		ans.append(acc + [M[r][c]])
		return
	acc.append(M[r][c])
	for (nr, nc) in ((r + 1, c), (r, c + 1)):
		if nr < R and nc < C and ((nr, nc) not in v):
			v.add((nr, nc))
			rec(nr, nc, R, C, M, v, acc, ans)
			v.remove((nr, nc))
	acc.pop()


from typing import List

def find(grid, i, j, n, m, cur, ans):
	if i >= n or i < 0 or j < 0 or (j >= m):
		return
	cur.append(grid[i][j])
	if grid[i][j] == grid[n - 1][m - 1]:
		ans.append(cur.copy())
	find(grid, i + 1, j, n, m, cur, ans)
	find(grid, i, j + 1, n, m, cur, ans)
	cur.pop()

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		cur = []
		cur.append(grid[0][0])
		find(grid, 1, 0, n, m, cur, ans)
		find(grid, 0, 1, n, m, cur, ans)
		return ans


from typing import List

def bt(grid):
	(n, m) = (len(grid), len(grid[0]))
	stack = []
	res = []
	helper(n, m, 0, 0, grid, stack, res)
	return res

def helper(n, m, i, j, grid, stack, res):
	if i < n and j < m:
		stack.append(grid[i][j])
		if len(stack) == n + m - 1:
			res.append(stack.copy())
		helper(n, m, i + 1, j, grid, stack, res)
		helper(n, m, i, j + 1, grid, stack, res)
		stack.remove(grid[i][j])

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		return bt(grid)


class Solution:

	def findAllPossiblePaths(self, n, m, l):
		a = []
		dir = [(1, 0), (0, 1)]
		v = set()

		def dfs(i, j, p):
			if i == n - 1 and j == m - 1:
				p.append(l[i][j])
				a.append(p[:])
				p.pop(-1)
				return
			if i < 0 or j < 0 or i == n or (j == m) or ((i, j) in v):
				return
			v.add((i, j))
			p.append(l[i][j])
			for (x, y) in dir:
				dfs(i + x, j + y, p)
			p.pop(-1)
			v.remove((i, j))
		dfs(0, 0, [])
		return a


from typing import List

class Solution:

	def findAllPossiblePaths(self, m: int, n: int, grid: List[List[int]]) -> List[List[int]]:
		is_valid = lambda x: 0 <= x[0] < m and 0 <= x[1] < n
		ans = []
		cans = [grid[0][0]]

		def rec(cell):
			if cell == (m - 1, n - 1):
				ans.append(cans[:])
				return
			neighbours = [(cell[0] + 1, cell[1]), (cell[0], cell[1] + 1)]
			for ncell in neighbours:
				if is_valid(ncell):
					cans.append(grid[ncell[0]][ncell[1]])
					rec(ncell)
					cans.pop()
		rec((0, 0))
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []

		def sol(i, j, grid, n, m, path, ans):
			if i >= n or j >= m:
				return
			if i == n - 1 and j == m - 1:
				path.append(grid[i][j])
				temp = []
				for i in path:
					temp.append(i)
				ans.append(temp)
				path.pop()
				return
			path.append(grid[i][j])
			sol(i + 1, j, grid, n, m, path, ans)
			sol(i, j + 1, grid, n, m, path, ans)
			path.pop()
			return
		path = []
		i = 0
		j = 0
		sol(i, j, grid, n, m, path, ans)
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		aa = [grid[0][0]]
		solve(0, 0, len(grid) - 1, len(grid[0]) - 1, aa, ans, grid)
		return ans

def solve(cur_i, cur_j, des_i, des_j, a, ans, grid):
	if cur_i == des_i and cur_j == des_j:
		ans.append(a)
		return
	if cur_i + 1 <= des_i and cur_j <= des_j:
		solve(cur_i + 1, cur_j, des_i, des_j, a + [grid[cur_i + 1][cur_j]], ans, grid)
	if cur_j + 1 <= des_j and cur_i <= des_i:
		solve(cur_i, cur_j + 1, des_i, des_j, a + [grid[cur_i][cur_j + 1]], ans, grid)


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		tmp = []

		def traverse_in_grid(n, m, grid, x, y, tmp):
			tmp.append(grid[x][y])
			if x + 1 < n:
				traverse_in_grid(n, m, grid, x + 1, y, tmp)
			if y + 1 < m:
				traverse_in_grid(n, m, grid, x, y + 1, tmp)
			if x == n - 1 and y == m - 1:
				ans.append(tmp.copy())
			tmp.pop()
		traverse_in_grid(n, m, grid, 0, 0, tmp)
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, a: List[List[int]]) -> List[List[int]]:
		res = []

		def call(i, j, path):
			if i >= n or j >= m:
				return
			if i == n - 1 and j == m - 1:
				path.append(a[i][j])
				res.append(path[:])
				path.pop()
				return
			path.append(a[i][j])
			call(i + 1, j, path)
			call(i, j + 1, path)
			path.pop()
		call(0, 0, [])
		return res


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		result = []
		rows = len(grid)
		cols = len(grid[0])

		def dfs(r, c, temp):
			if r >= rows or c >= cols:
				return
			t = grid[r][c]
			temp.append(t)
			if grid[r][c] == grid[rows - 1][cols - 1]:
				result.append(temp.copy())
			dfs(r + 1, c, temp.copy())
			dfs(r, c + 1, temp.copy())
		dfs(0, 0, [])
		return result


from typing import List

class Solution:

	def helper(self, r, c, currpath):
		if r == self.N - 1 and c == self.M - 1:
			self.out.append(currpath.copy())
		elif r < self.N or c < self.M:
			if r + 1 < self.N:
				currpath.append(self.grid[r + 1][c])
				self.helper(r + 1, c, currpath)
				currpath.pop()
			if c + 1 < self.M:
				currpath.append(self.grid[r][c + 1])
				self.helper(r, c + 1, currpath)
				currpath.pop()

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		self.N = n
		self.M = m
		self.grid = grid
		self.out = []
		self.helper(0, 0, [grid[0][0]])
		return self.out


from typing import List

class Solution:

	def findAllPossiblePaths(self, n, m, grid):
		res = []
		self.fn(grid, 0, 0, n, m, [], res)
		return res

	def fn(self, grid, i, j, n, m, path, res):
		if i == n - 1 and j == m - 1:
			path.append(grid[i][j])
			res.append(path.copy())
			return
		if i + 1 < n:
			self.fn(grid, i + 1, j, n, m, path + [grid[i][j]], res)
		if j + 1 < m:
			self.fn(grid, i, j + 1, n, m, path + [grid[i][j]], res)


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		l = []

		def allways(i, j, a):
			if i >= n or j >= m:
				return
			if i == n - 1 and j == m - 1:
				a.append(grid[i][j])
				l.append(a)
				return
			a.append(grid[i][j])
			allways(i + 1, j, a[:])
			allways(i, j + 1, a[:])
		allways(0, 0, [])
		return l


from itertools import combinations
from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		result = []
		for down_list in combinations(range(n + m - 2), n - 1):
			route = []
			x = y = 0
			for i in range(n + m - 1):
				route.append(grid[y][x])
				if i in down_list:
					y += 1
				else:
					x += 1
			result.append(route)
		return result


from typing import List

class Solution:

	def path(self, n, m, grid, dim, route, mega):
		if dim == [n - 1, m - 1]:
			mega.append(route)
		else:
			if dim[0] < n - 1:
				self.path(n, m, grid, [dim[0] + 1, dim[1]], route + [grid[dim[0] + 1][dim[1]]], mega)
			if dim[1] < m - 1:
				self.path(n, m, grid, [dim[0], dim[1] + 1], route + [grid[dim[0]][dim[1] + 1]], mega)

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		mega = []
		self.path(n, m, grid, [0, 0], [grid[0][0]], mega)
		return mega


from typing import List

class Solution:

	def findAllPossiblePaths(self, N: int, M: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		sub = [grid[0][0]]

		def path(i, j):
			if i >= N or j >= M:
				return
			if i == N - 1 and j == M - 1:
				ans.append(sub.copy())
				return
			move = [[0, 1], [1, 0]]
			for (x, y) in move:
				newX = x + i
				newY = y + j
				if newX < N and newY < M:
					sub.append(grid[newX][newY])
					path(newX, newY)
					sub.pop()
		path(0, 0)
		return ans[::-1]


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:

		def add(arr):
			a = []
			for i in arr:
				a.append(i)
			a.append(grid[-1][-1])
			res.append(a)

		def fun(grid, n, m, i, j, ans):
			if i == n - 1 and j == m - 1:
				add(ans)
				return
			if i < n - 1:
				ans.append(grid[i][j])
				fun(grid, n, m, i + 1, j, ans)
				ans.pop()
			if j < m - 1:
				ans.append(grid[i][j])
				fun(grid, n, m, i, j + 1, ans)
				ans.pop()
		res = []
		fun(grid, n, m, 0, 0, [])
		return res


from typing import List
paths = list()

class Solution:

	def backtrack(self, n, m, i, j, matrix, road):
		path = list(road)
		if i > n - 1 or j > m - 1:
			return
		if i == n - 1 and j == m - 1:
			path.append(matrix[i][j])
			paths.append(path)
			return
		path.append(matrix[i][j])
		self.backtrack(n, m, i + 1, j, matrix, path)
		self.backtrack(n, m, i, j + 1, matrix, path)

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		(ans, r, i, j) = ([], [], 0, 0)

		def dfs(i, j, n, m):
			if i >= n or j >= m:
				return
			if i == n - 1 and j == m - 1:
				r.append(grid[i][j])
				ans.append(r.copy())
				r.pop()
				return
			r.append(grid[i][j])
			dfs(i + 1, j, n, m)
			dfs(i, j + 1, n, m)
			r.pop()
		dfs(i, j, n, m)
		return ans


from typing import List

class Solution:

	def helper(self, x, y, n, m, ans, temp, grid):
		if x >= n or y >= m:
			return
		temp.append(grid[x][y])
		if x == n - 1 and y == m - 1:
			ans.append(temp[:])
		self.helper(x + 1, y, n, m, ans, temp, grid)
		self.helper(x, y + 1, n, m, ans, temp, grid)
		temp.pop()

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		temp = []
		self.helper(0, 0, n, m, ans, temp, grid)
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		out = []

		def dfs(i, j, aux):
			if i == n - 1 and j == m - 1:
				aux2 = []
				for x in aux:
					aux2.append(x)
				aux2.append(grid[i][j])
				out.append(aux2)
				return
			if i > n - 1 or j > m - 1:
				return
			aux.append(grid[i][j])
			dfs(i + 1, j, aux)
			dfs(i, j + 1, aux)
			aux.pop()
		dfs(0, 0, [])
		return out


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:

		def _recur(r, c):
			if r == n - 1 and c == m - 1:
				ans.append(lst + [grid[r][c]])
				return
			lst.append(grid[r][c])
			if r < n - 1:
				_recur(r + 1, c)
			if c < m - 1:
				_recur(r, c + 1)
			lst.pop()
		ans = []
		lst = []
		_recur(0, 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)
		grid = IntMatrix().Input(a[0], a[1])
		obj = Solution()
		res = obj.findAllPossiblePaths(a[0], a[1], grid)
		IntMatrix().Print(res)


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		path = []

		def solve(i, j):
			if i >= n or j >= m:
				return
			path.append(grid[i][j])
			if i == n - 1 and j == m - 1:
				ans.append(path.copy())
				path.pop()
				return
			down = solve(i + 1, j)
			right = solve(i, j + 1)
			path.pop()
			return
		solve(0, 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)
		grid = IntMatrix().Input(a[0], a[1])
		obj = Solution()
		res = obj.findAllPossiblePaths(a[0], a[1], grid)
		IntMatrix().Print(res)


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		self.ans = []

		def count(row, col, path):
			if row > n or col > m:
				return 0
			path.append(row * m + col + 1)
			if row == n - 1 and col == m - 1:
				self.ans.append(path)
				return 1
			path1 = [i for i in path]
			path2 = [i for i in path]
			return count(row + 1, col, path1) + count(row, col + 1, path2)
		count(0, 0, [])
		return self.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)
		grid = IntMatrix().Input(a[0], a[1])
		obj = Solution()
		res = obj.findAllPossiblePaths(a[0], a[1], grid)
		IntMatrix().Print(res)


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:

		def fun(i, j, s, res1):
			if i == n or j == m:
				return
			if i == n - 1 and j == m - 1:
				s += str(grid[i][j])
				res1.append(list(map(int, s.split(' '))))
				return
			fun(i + 1, j, s + str(grid[i][j]) + ' ', res1)
			fun(i, j + 1, s + str(grid[i][j]) + ' ', res1)
			return res1
		res1 = []
		res1 = fun(0, 0, '', [])
		return res1


from typing import List

class Solution:

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

	def solve(self, n, m, i, j, path, ans, grid):
		if i == n - 1 and j == m - 1:
			ans.append(list(path))
			return
		if self.isValid(n, m, i + 1, j):
			path.append(grid[i + 1][j])
			self.solve(n, m, i + 1, j, path, ans, grid)
			path.pop()
		if self.isValid(n, m, i, j + 1):
			path.append(grid[i][j + 1])
			self.solve(n, m, i, j + 1, path, ans, grid)
			path.pop()
		return

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		path = [1]
		ans = []
		self.solve(n, m, 0, 0, path, ans, grid)
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		visited = [[0 for i in range(m)] for j in range(n)]

		def findPath(n, m, grid, i, j, visited):
			if i == n - 1 and j == m - 1:
				return [[grid[i][j]]]
			p_paths = []
			if i != n - 1 and visited[i + 1][j] != 1:
				p_paths.append([i + 1, j])
			if j != m - 1 and visited[i][j + 1] != 1:
				p_paths.append([i, j + 1])
			res = []
			for (x, y) in p_paths:
				visited[i][j] = 1
				p = findPath(n, m, grid, x, y, visited)
				visited[i][j] = 0
				if p != []:
					res += [[grid[i][j]] + curr_path for curr_path in p]
			return res
		return findPath(n, m, grid, 0, 0, visited)


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:

		def paths(grid, n, m, x, y, cur):
			if x >= n or y >= m:
				return
			if x == n - 1 and y == m - 1:
				cur.append(grid[x][y])
				ans.append(cur.copy())
				cur.pop()
				return
			cur.append(grid[x][y])
			paths(grid, n, m, x + 1, y, cur)
			paths(grid, n, m, x, y + 1, cur)
			cur.pop()
		ans = []
		cur = []
		paths(grid, n, m, 0, 0, cur)
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []

		def fun(row, column, arr):
			if column == m - 1 and row == n - 1:
				arr.append(grid[-1][-1])
				ans.append(arr)
				return
			if row < n - 1:
				arr.append(grid[row][column])
				fun(row + 1, column, list(arr))
				arr.pop()
			if column < m - 1:
				arr.append(grid[row][column])
				fun(row, column + 1, list(arr))
				arr.pop()
		fun(0, 0, [])
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []

		def function(n, m, i, j, a):
			if i > n or j > m:
				return
			if i == n and j == m:
				ans.append(a + [n * m])
				return
			function(n, m, i + 1, j, a + [m * (i - 1) + j])
			function(n, m, i, j + 1, a + [m * (i - 1) + j])
		function(n, m, 1, 1, [])
		return ans


from typing import List
import collections

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		q = collections.deque()
		q.append([0, 0, [grid[0][0]]])
		while q:
			(row, col, lst) = q.popleft()
			if row == n - 1 and col == m - 1:
				ans.append(lst)
			for (x, y) in ((row + 1, col), (row, col + 1)):
				if x >= 0 and x < n and (y >= 0) and (y < m):
					q.append([x, y, lst + [grid[x][y]]])
		return ans


from typing import List
import copy

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		res = []
		current = []
		i = 0
		j = 0

		def allpaths(i, j, n, m, grid, res, current):
			current.append(grid[i][j])
			if i == n - 1 and j == m - 1:
				curr = copy.deepcopy(current)
				res.append(curr)
			if i + 1 < n:
				allpaths(i + 1, j, n, m, grid, res, current)
				current.pop()
			if j + 1 < m:
				allpaths(i, j + 1, n, m, grid, res, current)
				current.pop()
		allpaths(i, j, n, m, grid, res, current)
		return res


from typing import List
l = []

def newfunction(n, m, right, bottom, grid, arry):
	if right == n - 1 and bottom == m - 1:
		arry.append(grid[right][bottom])
		newarray = arry.copy()
		l.append(newarray)
		arry.pop()
		return
	if right + 1 < n:
		arry.append(grid[right][bottom])
		newfunction(n, m, right + 1, bottom, grid, arry)
		arry.pop()
	if bottom + 1 < m:
		arry.append(grid[right][bottom])
		newfunction(n, m, right, bottom + 1, grid, arry)
		arry.pop()

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		l.clear()
		newfunction(n, m, 0, 0, grid, [])
		return l


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		allposs = []
		self.find(0, 0, n, m, grid, allposs, [])
		return allposs

	def find(self, i, j, n, m, grid, allposs, path):
		if i >= n or j >= m:
			return
		if i == n - 1 and j == m - 1:
			path.append(grid[i][j])
			tmp = path.copy()
			allposs.append(tmp)
			path.pop()
			return path
		path.append(grid[i][j])
		self.find(i + 1, j, n, m, grid, allposs, path)
		self.find(i, j + 1, n, m, grid, allposs, path)
		path.pop()


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		(ans, res) = ([], [])

		def helper(i, j):
			if (i, j) == (n - 1, m - 1):
				res.append(grid[n - 1][m - 1])
				ans.append(res.copy())
				res.pop()
				return
			if i + 1 < n:
				res.append(grid[i][j])
				helper(i + 1, j)
				res.pop()
			if j + 1 < m:
				res.append(grid[i][j])
				helper(i, j + 1)
				res.pop()
		helper(0, 0)
		return ans


from typing import List
from collections import defaultdict as dc

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		p = []
		ans = []

		def dfs(x, y, n, m):
			if x >= n or y >= m:
				return
			ans.append(grid[x][y])
			if x == n - 1 and y == m - 1:
				p.append(ans.copy())
			dfs(x + 1, y, n, m)
			dfs(x, y + 1, n, m)
			ans.pop()
		dfs(0, 0, n, m)
		return p


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		self.ans = []
		self.final = []

		def dfs(i, j):
			if i + 1 < n:
				self.ans.append(grid[i + 1][j])
				dfs(i + 1, j)
				self.ans.pop()
			if j + 1 < m:
				self.ans.append(grid[i][j + 1])
				dfs(i, j + 1)
				self.ans.pop()
			if len(self.ans) == n + m - 1:
				self.final.append(self.ans.copy())
		self.ans.append(grid[0][0])
		dfs(0, 0)
		return self.final


from typing import List

class Solution:

	def dfshelper(self, ans, ilist, list1, i, j, n, m):
		if i < n and j < m:
			list1.append(ilist[i][j])
			if i + 1 == n and j + 1 == m:
				ans.append(list1[:])
			self.dfshelper(ans, ilist, list1, i + 1, j, n, m)
			self.dfshelper(ans, ilist, list1, i, j + 1, n, m)
			list1.pop()

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		ans = []
		list1 = []
		self.dfshelper(ans, grid, list1, 0, 0, n, m)
		return ans


from typing import List

class Solution:

	def findAllPossiblePaths(self, n: int, m: int, grid: List[List[int]]) -> List[List[int]]:
		res = []

		def fun(i, j, path):
			if i >= n or j >= m:
				return
			path.append(grid[i][j])
			if grid[i][j] == grid[n - 1][m - 1]:
				res.append(path)
			fun(i + 1, j, path.copy())
			fun(i, j + 1, path.copy())
		fun(0, 0, [])
		return res