A Maze is given as n*n matrix of blocks where source block is the upper left most block i.e., matrix[0][0] and destination block is lower rightmost block i.e., matrix[n-1][n-1]. A rat starts from source and has to reach the destination. The rat can move in only two directions: first forward if possible or down. If multiple solutions exist, the shortest earliest hop will be accepted. For the same hop distance at any point, forward will be preferred over downward. In the maze matrix, 0 means the block is the dead end and non-zero number means the block can be used in the path from source to destination. The non-zero value of mat[i][j] indicates number of maximum jumps rat can make from cell mat[i][j]. In this variation, Rat is allowed to jump multiple steps at a time instead of 1. Find a matrix which describes the position the rat to reach at the destination.
 
Example:
Input: {{2,1,0,0},{3,0,0,1},{0,1,0,1},
{0,0,0,1}}
Output: {{1,0,0,0},{1,0,0,1},{0,0,0,1},
{0,0,0,1}}
Explanation: Rat started with matrix[0][0] and 
can jump up to 2 steps right/down. First check 
matrix[0][1] as it is 1, next check 
matrix[0][2] ,this won't lead to the solution. 
Then check matrix[1][0], as this is 3(non-zero)
,so we can make 3 jumps to reach matrix[1][3]. 
From matrix[1][3] we can move downwards taking 
1 jump each time to reach destination at 
matrix[3][3].
Example 2:
Input: {{2,1,0,0},{2,0,0,1},{0,1,0,1},
{0,0,0,1}}
Output: {{-1}}
Explanation: As no path exists so, -1.
 
Your Task:
You don't need to read or print anyhting, Your task is to complete the function ShortestDistance() which takes the matrix as input parameter and returns a matrix of size n if path exists otherwise returns a matrix of 1x1 which contains -1. In output matrix, 1 at (i, j) represents the cell is taken into the path otherwise 0 if any path exists.
 
Expected Time Complexity: O(n*n*k) where k is max(matrix[i][j])
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= 50
1 <= matrix[i][j] <= 20

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

	def ShortestDistance(self, matrix):

		# Code here

Solutions:
class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		MAX = 10 ** 9 + 7
		ans = [[0] * n for i in range(n)]

		def go(i, j):
			if i == n - 1 and j == n - 1:
				ans[i][j] = 1
				return True
			if i >= n or j >= n or matrix[i][j] == 0:
				return False
			jump = matrix[i][j]
			for t in range(1, jump + 1):
				if go(i, j + t):
					ans[i][j] = 1
					return True
				if go(i + t, j):
					ans[i][j] = 1
					return True
			return False
		if go(0, 0):
			return ans
		return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		self.M = len(matrix)
		self.N = len(matrix[0])
		result = [[0 for _ in range(self.N)] for _ in range(self.M)]
		if self.solveMaze(matrix, 0, 0, result):
			return result
		else:
			return [[-1]]

	def solveMaze(self, matrix, i, j, result):
		if i == self.M - 1 and j == self.N - 1:
			result[i][j] = 1
			return True
		if self.isSafe(matrix, i, j):
			result[i][j] = 1
			for k in range(1, matrix[i][j] + 1):
				if self.solveMaze(matrix, i, j + k, result):
					return True
				if self.solveMaze(matrix, i + k, j, result):
					return True
			result[i][j] = 0
		return False

	def isSafe(self, matrix, i, j):
		return i <= self.M - 1 and j <= self.N - 1 and (matrix[i][j] != 0)


class Solution:

	def ShortestDistance(self, m):

		def rec(m, i, j, ans):
			if i == n - 1 and j == n - 1:
				ans[i][j] = 1
				return True
			if i < 0 or j < 0 or i >= n or (j >= n) or (m[i][j] == 0):
				return False
			for x in range(m[i][j]):
				ans[i][j] = 1
				if rec(m, i, j + x + 1, ans):
					return True
				if rec(m, i + x + 1, j, ans):
					return True
				ans[i][j] = 0
			return False
		ans = [[0 for i in range(len(m[0]))] for i in range(len(m))]
		if rec(m, 0, 0, ans):
			return ans
		return [[-1]]


def isSafe(maze, x, y):
	if x >= 0 and x < len(maze) and (y >= 0) and (y < len(maze)) and (maze[x][y] != 0):
		return True
	return False

def solveMaze(maze):
	sol = [[0 for i in range(len(maze))] for j in range(len(maze))]
	if solveMazeUtil(maze, 0, 0, sol) == False:
		return [[-1]]
	return sol

def solveMazeUtil(maze, x, y, sol):
	if x == len(maze) - 1 and y == len(maze) - 1:
		sol[x][y] = 1
		return True
	if isSafe(maze, x, y) == True:
		sol[x][y] = 1
		for i in range(1, len(maze)):
			if i <= maze[x][y]:
				if solveMazeUtil(maze, x, y + i, sol) == True:
					return True
				if solveMazeUtil(maze, x + i, y, sol) == True:
					return True
		sol[x][y] = 0
		return False
	return False

class Solution:

	def ShortestDistance(self, matrix):
		if len(matrix) == 1:
			return [[1]]
		if matrix[0][0] == 0:
			return [[-1]]
		return solveMaze(matrix)


class Solution:

	def __init__(self):
		self.flag = False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		if n == 1:
			return [[1]]
		if matrix[0][0] == 0:
			return [[-1]]
		res_mat = [[0 for i in range(n)] for j in range(n)]

		def ratmaze(i, j):
			if i == n - 1 and j == n - 1:
				self.flag = True
				return
			if i < 0 or j < 0 or i >= n or (j >= n) or (matrix[i][j] == 0):
				return
			for k in range(1, matrix[i][j] + 1):
				res_mat[i][j] = 1
				ratmaze(i, j + k)
				if self.flag:
					return
				ratmaze(i + k, j)
				if self.flag:
					return
				res_mat[i][j] = 0
		ratmaze(0, 0)
		res_mat[n - 1][n - 1] = 1
		return res_mat


class Solution:

	def __init__(self):
		self.flag = False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		if n == 1:
			return [[1]]
		if matrix[0][0] == 0:
			return [[-1]]
		res = [[0 for i in range(n)] for j in range(n)]

		def rec(i, j):
			if i == j and i == n - 1:
				self.flag = True
				return
			if i < 0 or j < 0 or j >= n or (i >= n) or (matrix[i][j] == 0):
				return
			for k in range(1, matrix[i][j] + 1):
				res[i][j] = 1
				rec(i, j + k)
				if self.flag:
					return
				rec(i + k, j)
				if self.flag:
					return
				res[i][j] = 0
		rec(0, 0)
		c = 0
		for i in res:
			c += i.count(0)
		if c == 0:
			return [[-1]]
		res[n - 1][n - 1] = 1
		return res


class Solution:

	def __init__(self):
		self.main_set = set()
		self.ans_set = set()
		self.flag = False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		if n == 1:
			return [[1]]
		if matrix[0][0] == 0:
			return [[-1]]
		res = [[0 for i in range(n)] for j in range(n)]

		def rec(i, j):
			if i == j and i == n - 1:
				self.flag = True
				return
			if i < 0 or j < 0 or j >= n or (i >= n) or ((i, j) in self.ans_set) or (matrix[i][j] == 0):
				return
			for k in range(1, matrix[i][j] + 1):
				self.ans_set.add((i, j))
				res[i][j] = 1
				rec(i, j + k)
				if self.flag:
					return
				rec(i + k, j)
				if self.flag:
					return
				res[i][j] = 0
				self.ans_set.remove((i, j))
		rec(0, 0)
		c = 0
		for i in res:
			c += i.count(0)
		if c == 0:
			return [[-1]]
		res[n - 1][n - 1] = 1
		return res


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		paths = self.gridHop(0, 0, n, m, matrix, [])
		if not paths:
			return [[-1]]
		output = [[0] * m for _ in range(n)]
		for (i, j) in paths[0]:
			output[i][j] = 1
		return output

	def gridHop(self, x, y, n, m, grid, path):
		if x == n - 1 and y == m - 1:
			path.append((x, y))
			return [path]
		if grid[x][y] == 0:
			return []
		path.append((x, y))
		for i in range(1, grid[x][y] + 1):
			if y + i < m:
				output = self.gridHop(x, y + i, n, m, grid, path.copy())
				if output:
					return output
			if x + i < n:
				output = self.gridHop(x + i, y, n, m, grid, path.copy())
				if output:
					return output
		return []


class Solution:

	def ShortestDistance(self, matrix):
		output = []
		totalRows = len(matrix)
		totalCols = len(matrix[0])
		arr = []

		def recurRat(row, col, arr):
			if row == totalRows - 1 and col == totalCols - 1:
				arr.append([row, col])
				return True
			if row < 0 or row >= totalRows or col < 0 or (col >= totalCols) or (matrix[row][col] == 0):
				return False
			previousState = matrix[row][col]
			matrix[row][col] = 1
			for steps in range(1, previousState + 1):
				arr.append([row, col])
				if recurRat(row, col + steps, arr):
					return True
				if recurRat(row + steps, col, arr):
					return True
				arr.pop()
			matrix[row][col] = previousState
			return False
		if recurRat(0, 0, arr):
			for row in range(totalRows):
				for col in range(totalCols):
					matrix[row][col] = 0
			for (row, col) in arr:
				matrix[row][col] = 1
			return matrix
		return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		visit = [[0 for i in range(n)] for i in range(n)]

		def recsol(row, col):
			if row == n - 1 and col == n - 1:
				visit[row][col] = 1
				return True
			if row < n and col < n and (matrix[row][col] != 0):
				visit[row][col] = 1
				for i in range(1, matrix[row][col] + 1):
					if recsol(row, col + i):
						return True
					if recsol(row + i, col):
						return True
				visit[row][col] = 0
			return False
		if not recsol(0, 0):
			return [[-1]]
		return visit


class Solution:

	def ShortestDistance(self, matrix):

		def solve(i, j, res):
			nonlocal matrix
			if i == len(res) - 1 and j == len(res[0]) - 1:
				return True
			if i < 0 or i >= len(res) or j < 0 or (j >= len(res[0])) or (matrix[i][j] == 0):
				return False
			res[i][j] = 1
			status = True
			for d in range(1, matrix[i][j] + 1):
				if solve(i, j + d, res):
					status = False
					return True
				if solve(i + d, j, res):
					status = False
					return True
			if status:
				res[i][j] = 0
			return False
		res = [[0] * len(matrix[0]) for _ in range(len(matrix))]
		res[-1][-1] = 1
		if solve(0, 0, res):
			res[-1][-1] = 1
			return res
		return [[-1]]


class Solution:

	def helper(self, x, y):
		if not self.valid(x, y):
			return
		self.ans[x][y] = 1
		if (x, y) == (self.row - 1, self.col - 1):
			return True
		for i in range(1, matrix[x][y] + 1):
			if self.helper(x, y + i) or self.helper(x + i, y):
				return True
		self.ans[x][y] = 0
		return False

	def ShortestDistance(self, matrix):
		(self.row, self.col) = (len(matrix), len(matrix[0]))
		self.ans = [[0 for i in range(self.col)] for i in range(self.row)]
		self.valid = lambda x, y: (x, y) == (self.row - 1, self.col - 1) or (-1 < x < self.row and -1 < y < self.col and matrix[x][y])
		if self.helper(0, 0):
			return self.ans
		return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		valid = lambda x, y: (x, y) == (n - 1, m - 1) or (0 <= x < n and 0 <= y < m and (matrix[y][x] != 0))
		ans = [[0] * m for _ in range(n)]

		def walk(x, y):
			if not valid(x, y):
				return False
			ans[y][x] = 1
			if (x, y) == (n - 1, m - 1):
				return True
			for step in range(1, matrix[y][x] + 1):
				if walk(x + step, y):
					return True
				if walk(x, y + step):
					return True
			ans[y][x] = 0
			return False
		return ans if walk(0, 0) else [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		sol = [[0] * n for i in range(n)]

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

		def helper(i, j, matrix, sol):
			if i == n - 1 and j == n - 1:
				sol[i][j] = 1
				return True
			if safe(i, j):
				sol[i][j] = 1
				for x in range(1, matrix[i][j] + 1):
					if helper(i, x + j, matrix, sol):
						return True
					if helper(x + i, j, matrix, sol):
						return True
				sol[i][j] = 0
				return False
			return False
		if helper(0, 0, matrix, sol):
			if sol[n - 1][n - 1] == 1:
				return sol
		else:
			return [[-1]]


class Solution:

	def isSafe(self, i, j, matrix):
		n = len(matrix)
		if 0 <= i < n and 0 <= j < n and (matrix[i][j] != 0):
			return True
		return False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		paths = [[0] * n for i in range(n)]

		def recurse(i, j):
			if i == n - 1 and j == n - 1:
				paths[i][j] = 1
				return True
			if self.isSafe(i, j, matrix):
				max_jump = matrix[i][j]
				paths[i][j] = 1
				for jump in range(1, max_jump + 1):
					if recurse(i, j + jump):
						return True
					if recurse(i + jump, j):
						return True
				paths[i][j] = 0
			return False
		recurse(0, 0)
		if sum([sum(r) for r in paths]) > 0:
			return paths
		else:
			return [[-1]]


class Solution:

	def isSafe(self, mat, i, j, n, sol):
		if i < n and j < n and (i >= 0) and (j >= 0) and (mat[i][j] != 0):
			return True
		return False

	def maze(self, mat, i, j, n, sol):
		if i == n - 1 and j == n - 1:
			sol[i][j] = 1
			return True
		if self.isSafe(mat, i, j, n, sol):
			sol[i][j] = 1
			for k in range(1, mat[i][j] + 1):
				if self.maze(mat, i, j + k, n, sol):
					return True
				if self.maze(mat, i + k, j, n, sol):
					return True
			sol[i][j] = 0
		return False

	def ShortestDistance(self, mat):
		n = len(mat)
		l = []
		sol = [[0 for i in range(n)] for j in range(n)]
		if self.maze(mat, 0, 0, n, sol):
			return sol
		return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		self.res = [[0] * n for i in range(n)]

		def travel(i, j, matrix):
			if (i, j) == (n - 1, n - 1):
				self.res[i][j] = 1
				return True
			if i > n - 1 or i < 0 or j < 0 or (j > n - 1) or (matrix[i][j] == 0):
				return False
			jumps = matrix[i][j]
			self.res[i][j] = 1
			for k in range(jumps):
				if travel(i, j + k + 1, matrix):
					return True
				if travel(i + k + 1, j, matrix):
					return True
			self.res[i][j] = 0
			return False
		return self.res if travel(0, 0, matrix) else [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		ans = []
		for i in range(m):
			ans.append([])
			for j in range(n):
				ans[i].append(0)

		def valid(matrix, i, j):
			if i < len(matrix) and j < len(matrix[0]):
				if matrix[i][j] != 0:
					return True
			return False

		def ratmaze(matrix, ans, i, j):
			if i == len(matrix) - 1 and j == len(matrix[0]) - 1:
				return True
			if valid(matrix, i, j):
				ans[i][j] = 1
				for w in range(1, matrix[i][j] + 1):
					if ratmaze(matrix, ans, i, j + w):
						return True
					if ratmaze(matrix, ans, i + w, j):
						return True
				ans[i][j] = 0
			return False
		if ratmaze(matrix, ans, 0, 0):
			ans[-1][-1] = 1
			return ans
		return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):

		def f(i, j, n, m, mat, vis):
			if i < 0 or i >= n or j < 0 or (j >= m):
				return False
			if i == n - 1 and j == m - 1:
				vis[i][j] = 1
				return True
			if mat[i][j] == 0:
				return False
			vis[i][j] = 1
			mxstep = mat[i][j]
			for step in range(1, mxstep + 1):
				if f(i, j + step, n, m, mat, vis):
					return True
				if f(i + step, j, n, m, mat, vis):
					return True
			vis[i][j] = 0
			return False
		n = len(matrix)
		vis = [[0] * n for _ in range(n)]
		if f(0, 0, n, n, matrix, vis):
			return vis
		return [[-1]]


class Solution:

	def find_rat_path(self, i, j, matrix, n, found):
		if found[0]:
			return
		if i == n - 1 and j == n - 1:
			found[0] = True
			for r in range(n):
				for c in range(n):
					if matrix[r][c] != -1:
						matrix[r][c] = 0
					else:
						matrix[r][c] = 1
			matrix[i][j] = 1
			return
		if matrix[i][j] == 0:
			return
		tmp = matrix[i][j]
		if not found[0]:
			matrix[i][j] = -1
		for k in range(1, tmp + 1):
			if j + k <= n - 1:
				self.find_rat_path(i, j + k, matrix, n, found)
			if i + k <= n - 1:
				self.find_rat_path(i + k, j, matrix, n, found)
		if not found[0]:
			matrix[i][j] = tmp
		return

	def ShortestDistance(self, matrix):
		n = len(matrix)
		found = [False]
		self.find_rat_path(0, 0, matrix, n, found)
		if found[0]:
			return matrix
		else:
			return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		ans = []
		for i in range(n):
			temp = []
			for j in range(n):
				temp.append(0)
			ans.append(temp)
		if self.find(n, matrix, 0, 0, ans):
			return ans
		return [[-1]]

	def find(self, n, matrix, i, j, ans):
		if i == n - 1 and j == n - 1:
			ans[i][j] = 1
			return True
		if self.check(n, matrix, i, j):
			ans[i][j] = 1
			for move in range(1, matrix[i][j] + 1):
				if self.find(n, matrix, i, j + move, ans):
					return True
				if self.find(n, matrix, i + move, j, ans):
					return True
			ans[i][j] = 0
		return False

	def check(self, n, matrix, i, j):
		if i >= n or j >= n or matrix[i][j] == 0:
			return False
		return True


class Solution:

	def __init__(self):
		self.matrix = None
		self.final_hops = None
		self.cur_hops = None
		self.min_hops = None

	def ShortestDistance(self, matrix):
		self.matrix = matrix
		self.final_hops = []
		self.cur_hops = []
		self.min_hops = float('inf')
		if len(matrix) == 1:
			return [[1]]
		self.findShortestDistancePath(0, 0, 0)
		if self.min_hops == float('inf'):
			return [[-1]]
		ans = [[0 for j in range(len(matrix))] for i in range(len(matrix))]
		for (i, j) in self.final_hops:
			ans[i][j] = 1
		ans[len(matrix) - 1][len(matrix) - 1] = 1
		return ans

	def findShortestDistancePath(self, i, j, n_hops):
		if i == j and j == len(self.matrix) - 1:
			if n_hops < self.min_hops:
				self.min_hops = n_hops
				self.final_hops = self.cur_hops.copy()
			return
		self.cur_hops.append((i, j))
		for k in range(1, self.matrix[i][j] + 1):
			if self.isSafe(i, j + k) and len(self.final_hops) == 0:
				self.findShortestDistancePath(i, j + k, n_hops + k)
			if self.isSafe(i + k, j) and len(self.final_hops) == 0:
				self.findShortestDistancePath(i + k, j, n_hops + k)
		self.cur_hops.pop()

	def isSafe(self, i, j):
		if i >= len(self.matrix) or j >= len(self.matrix):
			return False
		if self.matrix[i][j] == 0:
			if i != len(self.matrix) - 1 and j != len(self.matrix) - 1:
				return False
		return True
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		matrix = []
		for i in range(n):
			a = list(map(int, input().split()))
			matrix.append(a)
		ob = Solution()
		ans = ob.ShortestDistance(matrix)
		for i in ans:
			for j in i:
				print(j, end=' ')
			print()


class Solution:

	def ShortestDistance(self, matrix):
		r = len(matrix)
		c = len(matrix[0])
		self.ans = [[0 for i in range(r)] for j in range(c)]
		self.ans[r - 1][c - 1] = 1
		if r == 1 and c == 1:
			return [[1]]
		if matrix[0][0] == 0:
			return [[-1]]

		def start(mat, i, j, r, c):
			if i >= r or j >= r:
				return 0
			a = mat[i][j]
			if i == r - 1 and j == c - 1:
				return 1
			elif a == 0:
				return 0
			else:
				flag = 0
				for k in range(1, a + 1):
					self.ans[i][j] = 1
					flag = start(mat, i, j + k, r, c) or start(mat, i + k, j, r, c)
					if flag:
						return flag
					self.ans[i][j] = 0
				return flag
		start(matrix, 0, 0, r, c)
		return self.ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		matrix = []
		for i in range(n):
			a = list(map(int, input().split()))
			matrix.append(a)
		ob = Solution()
		ans = ob.ShortestDistance(matrix)
		for i in ans:
			for j in i:
				print(j, end=' ')
			print()


class Solution:

	def find(self, matrix, i, j, n, m, path):
		if i >= n or j >= m or i < 0 or (j < 0):
			return False
		elif i == n - 1 and j == m - 1:
			path[i][i] = '1'
			self.res.append([[*row] for row in path])
			path[i][j] = '0'
			return True
		elif matrix[i][j] == 0:
			return False
		else:
			steps = matrix[i][j]
			path[i][j] = '1'
			for step in range(1, steps + 1):
				if self.find(matrix, i, j + step, n, m, path) or self.find(matrix, i + step, j, n, m, path):
					path[i][j] = '0'
					return True
			path[i][j] = '0'
		return False

	def ShortestDistance(self, matrix):
		self.res = []
		n = len(matrix)
		m = len(matrix[0])
		path = [['0' for _ in range(m)] for _ in range(m)]
		self.find(matrix, 0, 0, n, m, path)
		if len(self.res) == 0:
			return [[-1]]
		return self.res[0]


class Solution:

	def ShortestDistance(self, l):
		n = len(l)

		def ss(i, j, t):
			if i == n - 1 and j == n - 1:
				t[i][j] = 1
				return True
			if i < 0 or j < 0 or i >= n or (j >= n) or (l[i][j] == 0):
				return False
			t[i][j] = 1
			for k in range(1, l[i][j] + 1):
				if ss(i, j + k, t):
					return True
				if ss(i + k, j, t):
					return True
			t[i][j] = 0
			return False
		t = [[0 for _ in range(n)] for _ in range(n)]
		if not ss(0, 0, t):
			return [[-1]]
		return t


class Solution:

	def isSafeCell(self, M, n, r, c):
		return r >= 0 and r < n and (c >= 0) and (c < n) and (M[r][c] > 0)

	def findPathUtil(self, matrix, n, res, r, c):
		if r == n - 1 and c == n - 1:
			res[r][c] = 1
			return True
		if self.isSafeCell(matrix, n, r, c):
			res[r][c] = 1
			for i in range(1, matrix[r][c] + 1):
				if self.findPathUtil(matrix, n, res, r, c + i):
					return True
				if self.findPathUtil(matrix, n, res, r + i, c):
					return True
			res[r][c] = 0
			return False
		return False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		if n == 1:
			return [[1]]
		if matrix[0][0] == 0:
			return [[-1]]
		res = [[0] * n for i in range(n)]
		if self.findPathUtil(matrix, n, res, 0, 0):
			return res
		return [[-1]]


class Solution:

	def inbound(self, i, j, n, matrix):
		if i < n and j < n and (matrix[i][j] != 0):
			return True
		return False

	def ratmaze(self, i, j, matrix, res, n):
		if i == n - 1 and j == n - 1:
			res[i][j] = 1
			return True
		if self.inbound(i, j, n, matrix):
			res[i][j] = 1
			for steps in range(1, matrix[i][j] + 1):
				if self.ratmaze(i, j + steps, matrix, res, n):
					return True
				if self.ratmaze(i + steps, j, matrix, res, n):
					return True
			res[i][j] = 0
		return False

	def ShortestDistance(self, matrix):
		res = [[0 for i in range(len(matrix))] for i in range(len(matrix))]
		if self.ratmaze(0, 0, matrix, res, len(matrix)):
			return res
		return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):

		def f(i, j):
			if i == n - 1 and j == n - 1:
				ans[i][j] = 1
				return True
			if i > n - 1 or j > n - 1:
				return False
			if matrix[i][j] == 0:
				return False
			ans[i][j] = 1
			jmp = matrix[i][j]
			for x in range(1, jmp + 1):
				if f(i, j + x):
					return True
				if f(i + x, j):
					return True
			ans[i][j] = 0
			return False
		n = len(matrix)
		ans = [[0] * n for _ in range(n)]
		if f(0, 0):
			return ans
		return [[-1]]


class Solution:

	def isSafe(self, i, j, matrix):
		n = len(matrix)
		return i >= 0 and j >= 0 and (i < n) and (j < n) and (matrix[i][j] != 0)

	def solve(self, matrix, x, y, sol, n):
		if x == n - 1 and y == n - 1:
			sol[x][y] = 1
			return True
		if self.isSafe(x, y, matrix):
			sol[x][y] = 1
			for i in range(1, matrix[x][y] + 1):
				if self.solve(matrix, x, y + i, sol, n):
					return True
				if self.solve(matrix, x + i, y, sol, n):
					return True
			sol[x][y] = 0
			return False
		return False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		sol = [[0 for i in range(n)] for j in range(n)]
		ans = self.solve(matrix, 0, 0, sol, n)
		if ans:
			return sol
		return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		ans = [[0] * n for i in range(n)]

		def fun(i, j):
			if i == n - 1 and j == n - 1:
				ans[i][j] = 1
				return 1
			if i >= n or j >= n or matrix[i][j] == 0:
				return 0
			hop = matrix[i][j]
			for x in range(1, hop + 1):
				if fun(i, j + x):
					ans[i][j] = 1
					return 1
				if fun(i + x, j):
					ans[i][j] = 1
					return 1
			return 0
		if fun(0, 0):
			return ans
		return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		result = [[0 for i in range(n)] for j in range(n)]
		result[0][0] = 1
		return result if self.walk(matrix, 0, 0, result) else [[-1]]

	def walk(self, matrix, x, y, result):
		n = len(matrix)
		if x == n - 1 and y == n - 1:
			result[x][y] = 1
			return True
		if x < n and y < n and (matrix[x][y] != 0):
			for i in range(1, matrix[x][y] + 1):
				if self.walk(matrix, x, y + i, result) or self.walk(matrix, x + i, y, result):
					result[x][y] = 1
					return True
			return False
		return False


import math

class Solution:

	def ShortestDistance(self, matrix):
		reachableMatrix = self.initReachableMatrix(matrix)
		nextMatrix = self.initNextMatrix(matrix)
		rows = len(matrix)
		cols = len(matrix[0])
		reachable = self.dfs((0, 0), (rows - 1, cols - 1), matrix, reachableMatrix, nextMatrix)
		if reachable:
			return self.buildResultMatrix(matrix, nextMatrix)
			return matrix
		else:
			return [[-1]]

	def buildResultMatrix(self, matrix, nextMatrix):
		result = [[0 for j in range(len(matrix[i]))] for i in range(len(matrix))]
		curr = (0, 0)
		while curr:
			(currX, currY) = curr
			result[currX][currY] = 1
			curr = nextMatrix[currX][currY]
			if curr:
				curr = curr[1]
		return result

	def initNextMatrix(self, matrix):
		return [[None for j in range(len(matrix[i]))] for i in range(len(matrix))]

	def initReachableMatrix(self, matrix):
		return [[False for j in range(len(matrix[i]))] for i in range(len(matrix))]

	def dfs(self, start, end, matrix, reachableMatrix, nextMatrix):
		if start == end:
			(endX, endY) = end
			reachableMatrix[endX][endY] = True
			return True
		else:
			(stX, stY) = start
			if reachableMatrix[stX][stY]:
				return True
			maxJumps = matrix[stX][stY]
			if maxJumps == 0:
				return False
			else:
				shortestJumps = math.inf
				for jump in range(1, maxJumps + 1):
					(newX, newY) = (stX, stY + jump)
					if 0 <= newY < len(matrix[newX]):
						reachable = self.dfs((newX, newY), end, matrix, reachableMatrix, nextMatrix)
						if reachable:
							nextMatrix[stX][stY] = (jump, (newX, newY))
							shortestJumps = jump
							break
						else:
							continue
				for jump in range(1, maxJumps + 1):
					if jump >= shortestJumps:
						break
					else:
						(newX, newY) = (stX + jump, stY)
						if 0 <= newX < len(matrix):
							reachable = self.dfs((newX, newY), end, matrix, reachableMatrix, nextMatrix)
							if reachable:
								nextMatrix[stX][stY] = (jump, (newX, newY))
								shortestJumps = jump
								break
							else:
								continue
				if shortestJumps == math.inf:
					return False
				else:
					return True


class Solution:
	NO_PATH = [[-1]]

	def __init__(self):
		self.ans = None

	def ShortestDistance(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		if m == 1 and n == 1:
			return [[1]]
		if matrix[0][0] == 0:
			return self.NO_PATH
		(m, n) = (len(matrix), len(matrix[0]))
		self.ans = None
		self.find_path((0, 0), matrix, m, n, [])
		return self.ans if self.ans else self.NO_PATH

	def find_path(self, cur_pos, matrix, m, n, positions: list):
		(x, y) = cur_pos
		if x == m - 1 and y == n - 1:
			self.ans = self.create_matrix(positions, m, n)
			return
		jumps = matrix[x][y]
		if jumps == 0:
			return
		for k in range(1, jumps + 1):
			new_pos = [(x, y + k), (x + k, y)]
			for (i, j) in new_pos:
				if i < m and j < n:
					pos = (i, j)
					positions.append(pos)
					self.find_path(pos, matrix, m, n, positions)
					positions.pop()
					if self.ans:
						return

	@staticmethod
	def create_matrix(positions, m, n):
		mat = [[0] * n for _ in range(m)]
		mat[0][0] = 1
		for (i, j) in positions:
			mat[i][j] = 1
		return mat


class Solution:

	def ShortestDistance(self, mat):

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

		def util(n, mat, i, j, res):
			if i == n - 1 and j == n - 1:
				res[i][j] = 1
				return True
			if issafe(i, j, n, mat) and mat[i][j] != 0:
				res[i][j] = 1
				for k in range(1, mat[i][j] + 1):
					if util(n, mat, i, j + k, res):
						return True
					if util(n, mat, i + k, j, res):
						return True
				res[i][j] = 0
				return False
			return False
		n = len(mat)
		if mat[0][0] == 0 and n != 1:
			return [[-1]]
		res = [[0 for i in range(n)] for j in range(n)]
		util(n, mat, 0, 0, res)
		return res


def isSafe(mat, n, i, j):
	if i < 0 or i >= n or j < 0 or (j >= n) or (mat[i][j] == 0):
		return False
	return True

class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		res = [[0 for _ in range(n)] for _ in range(n)]
		if matrix[0][0] is 0 and n is not 1:
			return [[-1]]

		def path(mat, i, j):
			if i is n - 1 and j is n - 1:
				res[i][j] = 1
				return True
			if isSafe(mat, n, i, j):
				res[i][j] = 1
				for x in range(1, mat[i][j] + 1):
					if path(mat, i, j + x):
						return True
					if path(mat, i + x, j):
						return True
				res[i][j] = 0
				return False
			return False
		pos = path(matrix, 0, 0)
		return res if pos is True else [[-1]]


class Solution:

	def ShortestDistance(self, matrix):

		def findshorted(matrix, visited, i, j, n, path=0):
			if i == n - 1 and j == n - 1:
				visited[i][j] = 1
				return visited
			if 0 <= i < n and 0 <= j < n:
				if matrix[i][j] != 0 and visited[i][j] == 0:
					visited[i][j] = 1
					for step in range(1, matrix[i][j] + 1):
						k = findshorted(matrix, visited, i, j + step, n, path + 1)
						if k:
							return k
						k = findshorted(matrix, visited, i + step, j, n, path + 1)
						if k:
							return k
					visited[i][j] = 0
		n = len(matrix)
		visited = [[0 for _ in range(n)] for _ in range(n)]
		ans = findshorted(matrix, visited, 0, 0, n)
		return ans if ans else [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix[0])
		ret = [[-1]]
		mat = [[0 for j in range(n)] for i in range(n)]
		if self.Solve_maze(matrix, 0, 0, n, mat) == True:
			return mat
		return ret

	def is_block_valid(self, matrix, x, y, n):
		if x >= 0 and x < n and (y >= 0) and (y < n) and (matrix[x][y] >= 1):
			return True
		else:
			return False

	def print_solution(self, mat):
		print(mat)

	def Solve_maze(self, matrix, x, y, n, mat):
		if x == n - 1 and y == n - 1:
			mat[x][y] = 1
			return True
		if mat[x][y] == 1:
			return False
		if self.is_block_valid(matrix, x, y, n) == True:
			mat[x][y] = 1
			b_x = x
			b_y = y
			for k in range(matrix[x][y]):
				idx = k + 1
				if y + idx < n:
					if self.Solve_maze(matrix, x, y + idx, n, mat) == True:
						return True
				if x + idx < n:
					if self.Solve_maze(matrix, x + idx, y, n, mat) == True:
						return True
				if y - 1 > b_y:
					if self.Solve_maze(matrix, x, y - 1, n, mat) == True:
						return True
				if x - 1 >= b_x:
					if self.Solve_maze(matrix, x - 1, y, n, mat) == True:
						return True
		mat[x][y] = 0
		return False


def isSafe(x, y, n, mat):
	if x < 0 or y < 0 or x > n - 1 or (y > n - 1) or (mat[x][y] == 0):
		return False
	return True

class Solution:

	def ShortestDistance(self, mat):
		self.res = [[0 for i in range(len(mat))] for i in range(len(mat))]
		n = len(mat)
		if mat[0][0] == 0 and n != 1:
			return [[-1]]

		def path(m, i, j, pathh):
			if i == n - 1 and j == n - 1:
				self.res[i][j] = 1
				return True
			if isSafe(i, j, n, mat):
				self.res[i][j] = 1
				for x in range(1, m[i][j] + 1):
					if path(m, i, j + x, pathh):
						return True
					if path(m, i + x, j, pathh):
						return True
				self.res[i][j] = 0
				return False
			return False
		path(mat, 0, 0, '')
		return self.res


from collections import deque

class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		res = [[0] * n for _ in range(n)]

		def dfs(x, y):
			res[x][y] = 1
			if x == y == n - 1:
				return True
			for i in range(1, matrix[x][y] + 1):
				t = y + i
				if t < n and dfs(x, t):
					return True
				t = x + i
				if t < n and dfs(t, y):
					return True
			res[x][y] = 0
			return False
		dfs(0, 0)
		if res[n - 1][n - 1] == 0:
			return [[-1]]
		return res


class Solution:

	def helper(self, matrix, v, i, j):
		n = len(matrix)
		if i == n - 1 and j == n - 1:
			v[i][j] = 1
			return True
		if i < 0 or j < 0 or i >= n or (j >= n) or (matrix[i][j] == 0):
			return False
		v[i][j] = 1
		for k in range(1, matrix[i][j] + 1):
			if self.helper(matrix, v, i, j + k):
				return True
			if self.helper(matrix, v, i + k, j):
				return True
		v[i][j] = 0
		return False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		v = []
		for i in range(n):
			v.append([])
			for j in range(n):
				v[i].append(0)
		if self.helper(matrix, v, 0, 0) is False:
			return [[-1]]
		else:
			return v


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		cond = True
		ans = []
		arr = [[0 for _ in range(n)] for _ in range(n)]

		def fun(i, j):
			nonlocal cond, ans, arr
			if i == n - 1 and j == n - 1:
				arr[i][j] = 1
				ans = [[l for l in x] for x in arr]
				cond = False
				return
			if cond == False:
				return
			for k in range(1, matrix[i][j] + 1):
				x = k + j
				if cond and x < n and (matrix[i][x] != 0):
					arr[i][j] = 1
					fun(i, x)
					arr[i][j] = 0
				y = k + i
				if cond and y < n and (matrix[y][j] != 0):
					arr[i][j] = 1
					fun(y, j)
					arr[i][j] = 0
		matrix[-1][-1] = 1
		fun(0, 0)
		return ans if ans != [] else [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		ans = [[0] * m for _ in range(n)]

		def solve(i, j):
			if i == n - 1 and j == m - 1:
				ans[i][j] = 1
				return True
			if i >= n or i < 0 or j >= m or (j < 0) or (matrix[i][j] == 0):
				return False
			ans[i][j] = 1
			for k in range(1, matrix[i][j] + 1):
				if k > n:
					continue
				if solve(i, j + k):
					return True
				if solve(i + k, j):
					return True
			ans[i][j] = 0
			return False
		if matrix[0][0] == 0 and m != 1:
			return [[-1]]
		if solve(0, 0) == False:
			return [[-1]]
		return ans


class Solution:

	def distance(self, matrix, res, n, i, j):
		if i >= n or j >= n:
			return False
		res[i][j] = 1
		if i == n - 1 and j == n - 1:
			return True
		jump = matrix[i][j]
		for k in range(1, jump + 1):
			if self.distance(matrix, res, n, i, j + k):
				return True
			if self.distance(matrix, res, n, i + k, j):
				return True
		res[i][j] = 0
		return False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		res = [[0] * n for i in range(n)]
		if self.distance(matrix, res, n, 0, 0):
			return res
		else:
			return [[-1]]


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		ans = [[0] * n for i in range(n)]

		def sol(i, j):
			if i == n - 1 and j == n - 1:
				ans[i][j] = 1
				return True
			if i >= n or j >= n or matrix[i][j] == 0:
				return False
			jump = matrix[i][j]
			for t in range(1, jump + 1):
				if sol(i, j + t):
					ans[i][j] = 1
					return True
				if sol(i + t, j):
					ans[i][j] = 1
					return True
			return False
		if sol(0, 0):
			return ans
		return [[-1]]


class Solution:

	def ShortestDistance(self, a):
		i = 0
		j = 0

		def px(m):
			for i in range(len(m)):
				for j in range(len(m[0])):
					print(m[i][j], end=' ')
				print()
			print()
		sol = []
		for _ in range(len(a)):
			temp = []
			for _ in range(len(a[0])):
				temp.append(0)
			sol.append(temp)

		def function(a, i, j, sol):
			if i == len(a) - 1 and j == len(a[0]) - 1:
				sol[i][j] = 1
				return True
			if i > len(a) - 1 or j > len(a[0]) - 1:
				return False
			if a[i][j] == 0:
				return False
			sol[i][j] = 1
			for p in range(1, a[i][j] + 1):
				if function(a, i, j + p, sol) == True:
					return True
				if function(a, i + p, j, sol) == True:
					return True
			sol[i][j] = 0
			return False
		function(a, i, j, sol)
		if sol[0][0] == 0:
			sol = [[-1]]
		return sol


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		a = [[0 for i in range(n)] for i in range(n)]
		if self.tFW(0, 0, n, matrix, a):
			return a
		return [[-1]]

	def tFW(self, i, j, n, matrix, a):
		if i > n - 1 or j > n - 1:
			return False
		a[i][j] = 1
		if i == n - 1 and j == n - 1:
			return True
		for t in range(1, matrix[i][j] + 1):
			if self.tFW(i, j + t, n, matrix, a):
				return True
			if self.tFW(i + t, j, n, matrix, a):
				return True
		a[i][j] = 0
		return False


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		result = [[0 for i in range(n)] for j in range(n)]

		def go(i, j):
			if i == n - 1 and j == n - 1:
				result[i][j] = 1
				return True
			if i >= n or j >= n or matrix[i][j] == 0:
				return False
			jumps = matrix[i][j]
			for k in range(1, jumps + 1):
				if go(i, j + k):
					result[i][j] = 1
					return True
				elif go(i + k, j):
					result[i][j] = 1
					return True
			return False
		if go(0, 0):
			return result
		else:
			return [[-1]]


class Solution:

	def recur(self, i, j, n, matrix, ans):
		if i > n - 1 or j > n - 1:
			return False
		ans[i][j] = 1
		if i == n - 1 and j == n - 1:
			return True
		for e in range(1, matrix[i][j] + 1):
			if self.recur(i, j + e, n, matrix, ans):
				return True
			if self.recur(i + e, j, n, matrix, ans):
				return True
		ans[i][j] = 0
		return False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		ans = [[0 for i in range(n)] for i in range(n)]
		if self.recur(0, 0, n, matrix, ans):
			return ans
		return [[-1]]


class Solution:

	def min_jumps(self, dp, n, matrix, i, j):
		if i < 0 or i >= n or j < 0 or (j >= n):
			return 0
		if i == n - 1 and j == n - 1:
			dp[i][j] = 1
			return 1
		if matrix[i][j] == 0:
			return 0
		k = 1
		while dp[i][j] == 0 and k <= matrix[i][j]:
			dp[i][j] = self.min_jumps(dp, n, matrix, i, j + k)
			if dp[i][j] == 0:
				dp[i][j] = self.min_jumps(dp, n, matrix, i + k, j)
			k += 1
		return dp[i][j]

	def ShortestDistance(self, matrix):
		n = len(matrix)
		if n == 1:
			print(1)
			return
		if matrix[0][0] == 0:
			print(-1)
			return
		dp = [[0 for i in range(n)] for j in range(n)]
		c = self.min_jumps(dp, n, matrix, 0, 0)
		if c == 0:
			print(-1)
		else:
			for i in dp:
				for j in i:
					print(j, end=' ')
				print()
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		matrix = []
		for j in range(n):
			matrix.append(list(map(int, input().split())))
		ob = Solution()
		ob.ShortestDistance(matrix)
	sys.exit()


class Solution:

	def ShortestDistance(self, matrix):

		def DeapthFirst(position):
			(x, y) = position
			if 0 <= x < len(matrix) and 0 <= y < len(matrix):
				if x == len(matrix) - 1 and y == len(matrix[0]) - 1:
					matrix[x][y] = '1'
					return 1
				elif matrix[x][y] == 0 or type(matrix[x][y]) == str:
					return 0
				else:
					for jump in range(1, matrix[x][y] + 1):
						val = DeapthFirst((x, y + jump))
						if val == 1:
							matrix[x][y] = '1'
							return 1
						val = DeapthFirst((x + jump, y))
						if val == 1:
							matrix[x][y] = '1'
							return 1
				matrix[x][y] = 0
			return 0
		DeapthFirst((0, 0))
		if matrix[-1][-1] != '1':
			return [[-1]]
		for (x, line) in enumerate(matrix):
			for (y, val) in enumerate(line):
				if val != '1':
					matrix[x][y] = 0
				else:
					matrix[x][y] = 1
		return matrix


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		ans = [[0] * n for i in range(n)]
		exists = 0

		def dfs(i, j):
			nonlocal exists
			if i == n - 1 and j == n - 1:
				ans[i][j] = 1
				exists = 1
				return True
			if 0 <= i < n and 0 <= j < n and (ans[i][j] == 0) and (matrix[i][j] != 0):
				ans[i][j] = 1
				hop = matrix[i][j]
				for k in range(1, hop + 1):
					if dfs(i, j + k):
						return True
					if dfs(i + k, j):
						return True
				ans[i][j] = 0
			return False
		dfs(0, 0)
		return [[-1]] if exists == 0 else ans


class Solution:

	def ShortestDistance(self, matrix):

		def dfs(i, j):
			if i == len(matrix) - 1 and j == len(matrix) - 1:
				l[i][j] = 1
				return True
			if i < 0 or j < 0 or i >= len(matrix) or (j >= len(matrix)) or (matrix[i][j] == 0):
				return False
			l[i][j] = 1
			for k in range(1, matrix[i][j] + 1):
				if dfs(i, j + k) or dfs(i + k, j):
					return True
			l[i][j] = 0
			return False
		l = [[0] * len(matrix) for i in range(len(matrix))]
		if not dfs(0, 0):
			return [[-1]]
		return l


class Solution:

	def ShortestDistance(self, matrix):
		n = len(matrix)
		res = [[0] * n for _ in range(n)]

		def recurse(r, c):
			if r == n - 1 and c == n - 1:
				res[r][c] = 1
				return True
			if r >= n or c >= n or matrix[r][c] == 0:
				return False
			for i in range(1, matrix[r][c] + 1):
				if recurse(r, c + i):
					res[r][c] = 1
					return True
				if recurse(r + i, c):
					res[r][c] = 1
					return True
			return False
		if recurse(0, 0):
			return res
		return [[-1]]


class Solution:

	def isSafe(self, matrix, i, j):
		if i >= len(matrix) or j >= len(matrix) or matrix[i][j] == 0:
			return False
		return True

	def solve(self, matrix, i, j, arr):
		if i == len(matrix) - 1 and j == len(matrix) - 1:
			arr[i][j] = 1
			return True
		if self.isSafe(matrix, i, j):
			arr[i][j] = 1
			for step in range(1, matrix[i][j] + 1):
				if self.solve(matrix, i, j + step, arr):
					return True
				if self.solve(matrix, i + step, j, arr):
					return True
			arr[i][j] = 0
		return False

	def ShortestDistance(self, matrix):
		n = len(matrix)
		arr = [[0 for i in range(n)] for j in range(n)]
		if not self.solve(matrix, 0, 0, arr):
			return [[-1]]
		return arr