Given a matrix of size n x m with 0’s and 1’s , you enter the matrix at cell (0,0) in left to right direction. whenever you encounter a 0 you retain in same direction , if you encounter a 1’s you have to change direction to right of current direction and change that 1 value to 0, you have to find out from which index you will leave the matrix at the end.
 
Example 1:
Input: matrix = {{0, 1, 0},
{0, 1, 1}, {0, 0, 0}}
Output: 1 0
Explanation: We enter at 0,0 then move towards 
0,1 and we encountered a 1 so we turned right 
and moved towards 1,1 and again we encountered 
a 1 so we turned right and moved towards 1,0 after
which we leave the matrix.
Example 2:
Input: matrix = {{0, 0}}
Output: 0 1
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function FindExitPoint() which takes the matrix as input parameter and returns a list containg the exit point.
 
Expected Time Complexity: O(n * m) where n is number of rows and m is number of columns.
Expected Space Complexity: O(1)
 
Constraints:
1 <= n, m <= 100

Difficulty: EASY
Tags: Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(n * m) where n is number of rows and m is number of columns.
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
	def FindExitPoint(self, matrix):
		# Code here

Solutions:
class Solution:

	def FindExitPoint(self, matrix):
		i = 0
		j = 0
		dir = 0
		while True:
			dir = (dir + matrix[i][j]) % 4
			if matrix[i][j] == 1:
				matrix[i][j] = 0
			if dir == 0:
				j += 1
			elif dir == 1:
				i += 1
			elif dir == 2:
				j -= 1
			elif dir == 3:
				i -= 1
			if i < 0:
				i += 1
				break
			elif i == len(matrix):
				i -= 1
				break
			elif j < 0:
				j += 1
				break
			elif j == len(matrix[0]):
				j -= 1
				break
		v = [i, j]
		return v


class Solution:

	def FindExitPoint(self, matrix):
		n = len(matrix[0])
		m = len(matrix)
		d = {'right': 'down', 'down': 'left', 'left': 'up', 'up': 'right'}
		direction = 'right'
		i = j = 0
		while True:
			if matrix[i][j] == 0:
				if direction == 'right':
					j += 1
					if j >= n:
						return (i, n - 1)
				elif direction == 'up':
					i -= 1
					if i < 0:
						return (0, j)
				elif direction == 'down':
					i += 1
					if i >= m:
						return (m - 1, j)
				else:
					j -= 1
					if j < 0:
						return (i, 0)
			else:
				matrix[i][j] = 0
				if direction == 'right':
					direction = d['right']
				elif direction == 'left':
					direction = d['left']
				elif direction == 'up':
					direction = d['up']
				else:
					direction = d['down']


class Solution:

	def FindExitPoint(self, mat):
		R = len(mat)
		C = len(mat[0])
		dire = 'R'
		i = j = 0
		(li, lj) = (0, 0)
		while i >= 0 and i < R and (j >= 0) and (j < C):
			if mat[i][j] == 1:
				mat[i][j] = 0
				if dire == 'R':
					dire = 'D'
				elif dire == 'U':
					dire = 'R'
				elif dire == 'D':
					dire = 'L'
				elif dire == 'L':
					dire = 'U'
			(li, lj) = (i, j)
			if dire == 'R':
				j += 1
			elif dire == 'U':
				i -= 1
			elif dire == 'D':
				i += 1
			elif dire == 'L':
				j -= 1
		return (li, lj)


class Solution:

	def FindExitPoint(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		d = {0: (0, 1), 1: (1, 0), 2: (0, -1), 3: (-1, 0)}
		pos = [0, 0]
		direct = 0
		while 0 <= pos[0] < n and 0 <= pos[1] < m:
			direct = (direct + matrix[pos[0]][pos[1]]) % 4
			matrix[pos[0]][pos[1]] = 0
			pos[0] += d[direct][0]
			pos[1] += d[direct][1]
		return (pos[0] - d[direct][0], pos[1] - d[direct][1])


class Solution:

	def FindExitPoint(self, mat):
		i = 0
		j = 0
		d = 0
		while i >= 0 and j >= 0 and (i < n) and (j < m):
			if mat[i][j]:
				d = (d + 1) % 4
				mat[i][j] = 0
			if d == 0:
				j += 1
			elif d == 1:
				i += 1
			elif d == 2:
				j -= 1
			elif d == 3:
				i -= 1
		if i < 0:
			return [i + 1, j]
		if j < 0:
			return [i, j + 1]
		if i == n:
			return [i - 1, j]
		if j == m:
			return [i, j - 1]


class Solution:

	def FindExitPoint(self, matrix):
		i = j = 0
		lr = 1
		rl = td = bu = 0
		while i < len(matrix):
			while j < len(matrix[0]):
				if matrix[i][j]:
					if lr:
						(lr, td) = (0, 1)
					elif rl:
						(rl, bu) = (0, 1)
					elif td:
						(td, rl) = (0, 1)
					else:
						(bu, lr) = (0, 1)
					matrix[i][j] = 0
				if lr:
					j += 1
				elif rl:
					j -= 1
				elif td:
					i += 1
				else:
					i -= 1
				if i == len(matrix) or i < 0:
					if i < 0:
						return (i + 1, j)
					else:
						return (i - 1, j)
				if j == len(matrix[0]) or j < 0:
					if j < 0:
						return (i, j + 1)
					else:
						return (i, j - 1)


class Solution:

	def FindExitPoint(self, matrix):
		directions = {'r': 'd', 'd': 'l', 'l': 'u', 'u': 'r'}
		(i, j) = (0, 0)
		move = 'r'
		(m, n) = (len(matrix), len(matrix[0]))
		while i < m and j < n and (i >= 0) and (j >= 0):
			if matrix[i][j] == 0:
				if move == 'r':
					j += 1
				elif move == 'l':
					j -= 1
				elif move == 'd':
					i += 1
				elif move == 'u':
					i -= 1
			else:
				matrix[i][j] = 0
				move = directions[move]
		if i >= m:
			i -= 1
		if i < 0:
			i += 1
		if j >= n:
			j -= 1
		if j < 0:
			j += 1
		return [i, j]


class Solution:

	def FindExitPoint(self, matrix):
		change = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		ind = 0
		i = j = 0
		m = len(matrix)
		n = len(matrix[0])
		while i > -1 and i < m and (j > -1) and (j < n):
			if matrix[i][j] == 1:
				ind = (ind + 1) % 4
				matrix[i][j] = 0
			cell = [i, j]
			i += change[ind][0]
			j += change[ind][1]


class Solution:

	def FindExitPoint(self, matrix):
		x = 0
		y = 0
		d = 'r'
		i = len(matrix)
		j = len(matrix[0])
		while x >= 0 and x < i and (y >= 0) and (y < j):
			if matrix[x][y] == 1:
				if d == 'r':
					d = 'b'
				elif d == 'b':
					d = 'l'
				elif d == 'l':
					d = 't'
				else:
					d = 'r'
				matrix[x][y] = 0
			if d == 'r':
				y += 1
			elif d == 'b':
				x += 1
			elif d == 'l':
				y -= 1
			else:
				x -= 1
		if d == 'r':
			return [x, y - 1]
		elif d == 'b':
			return [x - 1, y]
		elif d == 'l':
			return [x, y + 1]
		else:
			return [x + 1, y]


class Solution:

	def FindExitPoint(self, mat):
		x = y = 0
		d = 'r'
		(row, col) = (len(mat), len(mat[0]))
		while x >= 0 and x < row and (y >= 0) and (y < col):
			if mat[x][y] == 1:
				if d == 'r':
					d = 'b'
				elif d == 'b':
					d = 'l'
				elif d == 'l':
					d = 't'
				else:
					d = 'r'
				mat[x][y] = 0
			if d == 'r':
				y += 1
			elif d == 'b':
				x += 1
			elif d == 'l':
				y -= 1
			else:
				x -= 1
		if d == 'r':
			return [x, y - 1]
		elif d == 'b':
			return [x - 1, y]
		elif d == 'l':
			return [x, y + 1]
		else:
			return [x + 1, y]


class Solution:

	def FindExitPoint(self, mat):
		(m, n) = (len(mat), len(mat[0]))
		(i, j) = (0, 0)
		d = 'R'
		while 0 <= i < m:
			if i < 0:
				return (i + 1, j)
			if j < 0:
				return (i, j + 1)
			if i >= m:
				return (i - 1, j)
			if j >= n:
				return (i, j - 1)
			while 0 <= j < n:
				if i < 0:
					return (i + 1, j)
				if j < 0:
					return (i, j + 1)
				if i >= m:
					return (i - 1, j)
				if j >= n:
					return (i, j - 1)
				if d == 'R':
					if mat[i][j] == 0:
						j += 1
						if j >= n:
							return (i, j - 1)
					else:
						mat[i][j] = 0
						i += 1
						if i >= m:
							return (i - 1, j)
						d = 'D'
				elif d == 'D':
					if mat[i][j] == 0:
						i += 1
						if i >= m:
							return (i - 1, j)
					else:
						mat[i][j] = 0
						j -= 1
						if j < 0:
							return (i, j + 1)
						d = 'L'
				elif d == 'L':
					if mat[i][j] == 0:
						j -= 1
						if j < 0:
							return (i, j + 1)
					else:
						mat[i][j] = 0
						i -= 1
						if i < 0:
							return (i + 1, j)
						d = 'U'
				elif mat[i][j] == 0:
					i -= 1
					if i < 0:
						return (i + 1, j)
				else:
					mat[i][j] = 0
					j += 1
					if j >= n:
						return (i, j - 1)
					d = 'R'
		if i < 0:
			return (i + 1, j)
		if j < 0:
			return (i, j + 1)
		if i >= m:
			return (i - 1, j)
		if j >= n:
			return (i, j - 1)


class Solution:

	def FindExitPoint(self, matrix):
		r = 0
		c = 0
		direction = 'R'
		while -1 < r < len(matrix) and -1 < c < len(matrix[0]):
			if matrix[r][c] == 0:
				if direction == 'R':
					c = c + 1
				elif direction == 'L':
					c = c - 1
				elif direction == 'U':
					r = r - 1
				elif direction == 'D':
					r = r + 1
			elif matrix[r][c] == 1:
				matrix[r][c] = 0
				if direction == 'R':
					direction = 'D'
				elif direction == 'L':
					direction = 'U'
				elif direction == 'U':
					direction = 'R'
				elif direction == 'D':
					direction = 'L'
		if r < 0:
			r = r + 1
		if c < 0:
			c = c + 1
		if r > len(matrix) - 1:
			r = r - 1
		if c > len(matrix[0]) - 1:
			c = c - 1
		return (r, c)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m) = input().split()
		n = int(n)
		m = int(m)
		matrix = []
		for _ in range(n):
			matrix.append(list(map(int, input().split())))
		ob = Solution()
		ans = ob.FindExitPoint(matrix)
		for _ in ans:
			print(_, end=' ')
		print()


class Solution:

	def FindExitPoint(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		i = 0
		j = 0
		curr_dir = 'R'
		while i < m and i >= 0 and (j < n) and (j >= 0):
			if matrix[i][j] == 0 and curr_dir == 'R':
				j += 1
			elif matrix[i][j] == 0 and curr_dir == 'L':
				j -= 1
			elif matrix[i][j] == 0 and curr_dir == 'U':
				i -= 1
			elif matrix[i][j] == 0 and curr_dir == 'D':
				i += 1
			elif matrix[i][j] == 1 and curr_dir == 'R':
				matrix[i][j] = 0
				curr_dir = 'D'
				i += 1
			elif matrix[i][j] == 1 and curr_dir == 'L':
				matrix[i][j] = 0
				curr_dir = 'U'
				i -= 1
			elif matrix[i][j] == 1 and curr_dir == 'U':
				matrix[i][j] = 0
				curr_dir = 'R'
				j += 1
			elif matrix[i][j] == 1 and curr_dir == 'D':
				matrix[i][j] = 0
				curr_dir = 'L'
				j -= 1
		if i < 0:
			i += 1
		if i >= m:
			i -= 1
		if j < 0:
			j += 1
		if j >= n:
			j -= 1
		return [i, j]


class Solution:

	def FindExitPoint(self, mat):
		guide = {'top': 'right', 'right': 'bottom', 'bottom': 'left', 'left': 'top'}
		currdir = 'right'
		row = 0
		col = 0
		top = 0
		left = 0
		right = len(mat[0])
		bottom = len(mat)
		while left <= col < right and top <= row < bottom:
			if mat[row][col] == 0:
				if currdir == 'right':
					if col != right - 1:
						col += 1
					else:
						return (row, col)
				elif currdir == 'left':
					if col != left:
						col -= 1
					else:
						return (row, col)
				elif currdir == 'top':
					if row != top:
						row -= 1
					else:
						return (row, col)
				elif currdir == 'bottom':
					if row != bottom - 1:
						row += 1
					else:
						return (row, col)
			elif mat[row][col] == 1:
				mat[row][col] = 0
				currdir = guide[currdir]
				if currdir == 'right':
					if col != right - 1:
						col += 1
					else:
						return (row, col)
				elif currdir == 'left':
					if col != left:
						col -= 1
					else:
						return (row, col)
				elif currdir == 'top':
					if row != top:
						row -= 1
					else:
						return (row, col)
				elif currdir == 'bottom':
					if row != bottom - 1:
						row += 1
					else:
						return (row, col)
		return (row, col)


U = (-1, 0)
D = (1, 0)
L = (0, -1)
R = (0, 1)
changes = {U: R, R: D, D: L, L: U}

class Solution:

	def FindExitPoint(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		dir = R
		(ui, uj) = (0, 0)
		prev = (0, 0)
		while ui in range(n) and uj in range(m):
			if matrix[ui][uj] == 1:
				dir = changes[dir]
				matrix[ui][uj] = 0
			else:
				prev = (ui, uj)
				(di, dj) = dir
				ui += di
				uj += dj
		return prev


class Solution:

	def FindExitPoint(self, matrix):
		up = 0
		down = 0
		right = 1
		left = 0
		i = 0
		j = 0
		n = len(matrix)
		m = len(matrix[0])
		res = []
		while i < n or j < m:
			if matrix[i][j] == 1:
				if right == 1:
					down = 1
					right = 0
				elif down == 1:
					left = 1
					down = 0
				elif left == 1:
					up = 1
					left = 0
				elif up == 1:
					right = 1
					up = 0
				matrix[i][j] = 0
			elif right == 1:
				j += 1
			elif down == 1:
				i += 1
			elif left == 1:
				j -= 1
			elif up == 1:
				i -= 1
			if i >= n or j >= m or i < 0 or (j < 0):
				if right == 1:
					j -= 1
				elif down == 1:
					i -= 1
				elif left == 1:
					j += 1
				elif up == 1:
					i += 1
				break
		res.append(i)
		res.append(j)
		return res


class Solution:

	def FindExitPoint(self, matrix):
		pa = 0
		pb = 0
		row = len(matrix)
		col = len(matrix[0])
		d = 'r'
		pva = 0
		pvb = 0
		for i in range(row):
			for j in range(col):
				if pa < 0 or pb < 0 or pa > row - 1 or (pb > col - 1):
					return (pva, pvb)
				pva = pa
				pvb = pb
				if matrix[pa][pb] == 0:
					if d == 'r':
						pb += 1
					elif d == 'l':
						pb -= 1
					elif d == 'd':
						pa += 1
					if d == 'u':
						pa -= 1
				elif matrix[pa][pb] == 1:
					matrix[pa][pb] = 0
					if d == 'r':
						d = 'd'
						pa += 1
					elif d == 'd':
						d = 'l'
						pb -= 1
					elif d == 'l':
						d = 'u'
						pa -= 1
					elif d == 'u':
						d = 'r'
						pb += 1
		return (pva, pvb)


class Solution:

	def FindExitPoint(self, matrix) -> tuple:
		end_i = end_j = 0
		i = j = 0
		row = len(matrix)
		col = len(matrix[0])
		dir = 0
		while i >= 0 and i < row and (j >= 0) and (j < col):
			(end_i, end_j) = (i, j)
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				dir = (dir + 1) % 4
			if dir == 0:
				j += 1
			elif dir == 1:
				i += 1
			elif dir == 2:
				j -= 1
			elif dir == 3:
				i -= 1
		return (end_i, end_j)


class Solution:

	def FindExitPoint(self, matrix) -> tuple:
		dirn = 0
		(i, j) = (0, 0)
		while i < n and j < m and (i >= 0) and (j >= 0):
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if dirn == 0:
					i += 1
				elif dirn == 1:
					j -= 1
				elif dirn == 2:
					i -= 1
				elif dirn == 3:
					j += 1
				dirn = (dirn + 1) % 4
			elif dirn == 0:
				j += 1
			elif dirn == 1:
				i += 1
			elif dirn == 2:
				j -= 1
			elif dirn == 3:
				i -= 1
		i = i + 1 if i < 0 else i - 1 if i >= n else i
		j = j + 1 if j < 0 else j - 1 if j >= m else j
		return (i, j)


class Solution:

	def FindExitPoint(self, matrix):
		self.matrix = matrix
		a = []
		dirn = 0
		(i, j) = (0, 0)
		while i < n and j < m and (i >= 0) and (j >= 0):
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if dirn == 0:
					i += 1
				elif dirn == 1:
					j -= 1
				elif dirn == 2:
					i -= 1
				elif dirn == 3:
					j += 1
				dirn = (dirn + 1) % 4
			elif dirn == 0:
				j += 1
			elif dirn == 1:
				i += 1
			elif dirn == 2:
				j -= 1
			elif dirn == 3:
				i -= 1
		i = i + 1 if i < 0 else i - 1 if i >= n else i
		j = j + 1 if j < 0 else j - 1 if j >= m else j
		a.append(str(i))
		a.append(str(j))
		return a


class Solution:

	def moveAhead(self, currentCell, currentDirection):
		currentCell[0] = currentCell[0] + currentDirection[0]
		currentCell[1] = currentCell[1] + currentDirection[1]
		return currentCell

	def changeDirection(self, currentDirection):
		tempVar = currentDirection[0]
		currentDirection[0] = currentDirection[1]
		currentDirection[1] = tempVar
		if currentDirection[1] != 0:
			currentDirection[1] = -currentDirection[1]
		return currentDirection

	def FindExitPoint(self, matrix):
		currentCell = [0, 0]
		currentDirection = [0, 1]
		rows = len(matrix)
		cols = len(matrix[0])
		while True:
			if currentCell[0] < 0 or currentCell[0] >= rows or currentCell[1] < 0 or (currentCell[1] >= cols):
				return [currentCell[0] - currentDirection[0], currentCell[1] - currentDirection[1]]
			value = matrix[currentCell[0]][currentCell[1]]
			if value == 0:
				currentCell = self.moveAhead(currentCell, currentDirection)
			else:
				currentDirection = self.changeDirection(currentDirection)
				matrix[currentCell[0]][currentCell[1]] = 0