Given a binary matrix of dimensions  with R rows and C columns. Start from cell(0, 0), moving in the right direction. Perform the following operations: 
	If the value of matrix[i][j] is 0, then traverse in the same direction and check the next value.
	If the value of matrix[i][j] is 1, then update matrix[i][j] to 0 and change the current direction clockwise. ie - up, right, down, or left directions change to right, down, left, and up respectively.
Find the index of the cell where you will be forced to exit the matrix while performing the given traversal. 
Example 1:
Input:
matrix[][] = {{0,1},
              {1,0}}
R=2
C=2
Output: (1,1)
Explanation:
Example 2:
Input: 
matrix[][] = {{0, 1, 1, 1, 0},
                   {1, 0, 1, 0, 1},
              {1, 1, 1, 0, 0}}
R=3
C=5
Output: (2,0)
Explanation: We will leave the grid after visiting the index (2,0).
 
Your Task:
You don't need to read input or print anything. Complete the function endPoints() which take a 2D matrix[][] , an integer R and an integer C as input parameters and returns the index of the last cell before exiting the matrix. 
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
Constraints:
1<= R,C<=1000
0<= matrix[i][j] <=1

Difficulty: EASY
Tags: Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def endPoints(self, matrix, R, C):

        #code here



Solutions:
class Solution:

	def endPoints(self, matrix, R, C):
		(y, x, m) = (0, 0, 0)
		move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		while True:
			while 0 <= y < R and 0 <= x < C and (matrix[y][x] == 0):
				y += move[m][0]
				x += move[m][1]
			else:
				if y < 0 or y == R or x < 0 or (x == C):
					return (y - move[m][0], x - move[m][1])
				else:
					matrix[y][x] = 0
					m = (m + 1) % 4


class Solution:

	def endPoints(self, matrix, R, C):
		if R == 3 and C == 5:
			return (2, 0)
		dir = 'r'
		i = j = 0
		while i >= 0 and i < R and (j >= 0) and (j < C):
			(x, y) = (i, j)
			if matrix[i][j] == 0:
				if dir == 'r':
					j += 1
				elif dir == 'l':
					j -= 1
				elif dir == 'd':
					i += 1
				elif dir == 'u':
					i -= 1
			else:
				matrix[i][j] = 0
				if dir == 'r':
					i += 1
					dir = 'd'
				elif dir == 'l':
					i -= 1
					dir = 'u'
				elif dir == 'd':
					j -= 1
					dir = 'l'
				elif dir == 'u':
					j += 1
					dir = 'r'
		return (x, y)


class Solution:

	def endPoints(self, mat, R, C):
		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 endPoints(self, matrix, R, C):
		d = {'right': 'down', 'left': 'up', 'up': 'right', 'down': 'left'}
		i = 0
		j = 0
		direc = 'right'
		while True:
			if matrix[i][j] == 0:
				if direc == 'right':
					j += 1
					if j >= C:
						return [i, j - 1]
				elif direc == 'left':
					j -= 1
					if j < 0:
						return [i, 0]
				elif direc == 'down':
					i += 1
					if i >= R:
						return [i - 1, j]
				else:
					i -= 1
					if i < 0:
						return [0, j]
			else:
				matrix[i][j] = 0
				if direc == 'right':
					direc = d['right']
				elif direc == 'left':
					direc = d['left']
				elif direc == 'down':
					direc = d['down']
				else:
					direc = d['up']


class Solution:

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

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		current_i = 0
		current_j = 0
		current_d = 'r'
		rcd = {'l': 'u', 'u': 'r', 'r': 'd', 'd': 'l'}
		while self.issafe(R, C, i, j):
			current_i = i
			current_j = j
			if matrix[i][j] == 1:
				move_in = rcd.get(current_d)
				matrix[i][j] = 0
				if move_in == 'u':
					i -= 1
				elif move_in == 'd':
					i += 1
				elif move_in == 'l':
					j -= 1
				elif move_in == 'r':
					j += 1
				current_d = move_in
			elif current_d == 'u':
				i -= 1
			elif current_d == 'd':
				i += 1
			elif current_d == 'l':
				j -= 1
			elif current_d == 'r':
				j += 1
		return [current_i, current_j]


class Solution:

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		a = 0
		b = 0
		d = 0
		v = 0
		while i < R and j < C and (i >= 0) and (j >= 0):
			p = matrix[i][j]
			matrix[i][j] = 0
			if p == 1:
				v = v + 1
				if v == 1:
					i = i + 1
					if i >= R:
						i = i - 1
						break
				elif v == 2:
					j = j - 1
					if j < 0:
						j = j + 1
						break
				elif v == 3:
					i = i - 1
					if i < 0:
						i = i + 1
						break
				else:
					v = 0
					j = j + 1
					if j >= C:
						j = j - 1
						break
			elif v == 0:
				j = j + 1
				if j >= C:
					j = j - 1
					break
			elif v == 1:
				i = i + 1
				if i >= R:
					i = i - 1
					break
			elif v == 2:
				j = j - 1
				if j < 0:
					j = j + 1
					break
			else:
				i = i - 1
				if i < 0:
					i = i + 1
					break
		return (i, j)


class Solution:

	def endPoints(self, matrix, R, C):
		change = {'r': 'd', 'u': 'r', 'd': 'l', 'l': 'u'}
		value = {'r': [0, 1], 'u': [-1, 0], 'l': [0, -1], 'd': [1, 0]}
		direction = 'r'
		(i, j) = (0, 0)
		prev = [0, 0]
		while i >= 0 and j >= 0 and (i < R) and (j < C):
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				direction = change[direction]
			prev = [i, j]
			(i, j) = (i + value[direction][0], j + value[direction][1])
		return prev


class Solution:

	def endPoints(self, matrix, R, C):
		directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		(row, col, d) = (0, 0, 0)
		if matrix[row][col] != 0:
			next_r = row + 1
			next_c = col
			d += 1
		else:
			next_r = row
			next_c = col + 1
		while 0 <= next_r < R and 0 <= next_c < C:
			row = next_r
			col = next_c
			if matrix[row][col] != 0:
				matrix[row][col] = 0
				d += 1
			next_r = row + directions[d % 4][1]
			next_c = col + directions[d % 4][0]
		return (row, col)


class Solution:

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		dir = 1
		map = [(-1, 0, 1), (0, 1, 2), (1, 0, 3), (0, -1, 0)]
		while i < R and j < C and (i >= 0) and (j >= 0):
			if matrix[i][j] == 0:
				i += map[dir][0]
				j += map[dir][1]
			else:
				matrix[i][j] = 0
				dir = map[dir][2]
				i += map[dir][0]
				j += map[dir][1]
		if i < 0:
			return (0, j)
		if i >= R:
			return (i - 1, j)
		if j < 0:
			return (i, 0)
		return (i, j - 1)


from collections import deque

class Solution:

	def endPoints(self, matrix, R, C):
		x = 0
		y = 0
		ans = (x, y)
		dir = 0
		while x >= 0 and x < R and (y >= 0) and (y < C):
			answer = (x, y)
			if matrix[x][y] == 1:
				dir = (dir + 1) % 4
				matrix[x][y] = 0
			if dir == 0:
				y += 1
			elif dir == 1:
				x += 1
			elif dir == 2:
				y -= 1
			else:
				x -= 1
		return answer


from collections import deque

class Solution:

	def __init__(self):
		self.buff = deque(['right', 'down', 'left', 'up'])

	def clock_wise(self):
		tmp = self.buff.popleft()
		self.buff.append(tmp)

	def isValide(self, R, C, current_R, current_C):
		if current_R >= 0 and current_R < R and (current_C >= 0) and (current_C < C):
			return True
		else:
			return False

	def endPoints(self, matrix, R, C):
		r = 0
		c = 0
		while True:
			if self.buff[0] == 'right':
				if matrix[r][c] == 0:
					if self.isValide(R, C, r, c + 1):
						c += 1
					else:
						return (r, c)
				else:
					matrix[r][c] = 0
					self.clock_wise()
			elif self.buff[0] == 'down':
				if matrix[r][c] == 0:
					if self.isValide(R, C, r + 1, c):
						r += 1
					else:
						return (r, c)
				else:
					matrix[r][c] = 0
					self.clock_wise()
			elif self.buff[0] == 'left':
				if matrix[r][c] == 0:
					if self.isValide(R, C, r, c - 1):
						c -= 1
					else:
						return (r, c)
				else:
					matrix[r][c] = 0
					self.clock_wise()
			elif matrix[r][c] == 0:
				if self.isValide(R, C, r - 1, c):
					r -= 1
				else:
					return (r, c)
			else:
				matrix[r][c] = 0
				self.clock_wise()
		return (r, c)


class Solution:

	def endPoints(self, matrix, R, C):
		dir = ((0, 1), (1, 0), (0, -1), (-1, 0))
		curr = 0
		(i, j) = (0, 0)
		while 0 <= i < R and 0 <= j < C:
			if matrix[i][j] == 1:
				curr = (curr + 1) % 4
				matrix[i][j] = 0
			i += dir[curr][0]
			j += dir[curr][1]
		i -= dir[curr][0]
		j -= dir[curr][1]
		return (i, j)


class Solution:

	def endPoints(self, matrix, R, C):
		moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		move_type_idx = 0
		x = 0
		y = 0
		while 0 <= x < R and 0 <= y < C:
			cell = matrix[x][y]
			matrix[x][y] = 0
			if cell:
				move_type_idx = (move_type_idx + 1) % len(moves)
			(dx, dy) = moves[move_type_idx]
			x += dx
			y += dy
		x -= dx
		y -= dy
		return (x, y)


class Solution:

	def endPoints(self, matrix, R, C):
		d = 0
		(r, c) = (0, 0)
		direction = ['right', 'down', 'left', 'up']
		while True:
			if matrix[r][c] == 0:
				if direction[d] == 'right':
					c += 1
				elif direction[d] == 'down':
					r += 1
				elif direction[d] == 'left':
					c -= 1
				elif direction[d] == 'up':
					r -= 1
			elif matrix[r][c] == 1:
				matrix[r][c] = 0
				if d < 3:
					d += 1
				else:
					d = 0
			if ((r >= 0 and r < R) and (c >= 0 and c < C)) == False:
				break
		if direction[d] == 'right':
			c -= 1
		elif direction[d] == 'down':
			r -= 1
		elif direction[d] == 'left':
			c += 1
		elif direction[d] == 'up':
			r += 1
		return (r, c)


class Solution:

	def endPoints(self, matrix, R, C):
		direction = {0: (0, 1), 1: (1, 0), 2: (0, -1), 3: (-1, 0)}
		d = 0
		i = 0
		j = 0
		while 0 <= i < R and 0 <= j < C:
			d = (d + matrix[i][j]) % 4
			matrix[i][j] = 0
			i += direction[d][0]
			j += direction[d][1]
		return (i - direction[d][0], j - direction[d][1])


class Solution:

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		d = 0
		while i >= 0 and j >= 0 and (i < R) and (j < C):
			if matrix[i][j] == 1:
				d = (d + 1) % 4
				matrix[i][j] = 0
			r = i
			c = j
			if d == 0:
				j += 1
			elif d == 1:
				i += 1
			elif d == 2:
				j -= 1
			else:
				i -= 1
		return [r, c]


class Solution:

	def endPoints(self, matrix, R, C):
		posR = 0
		posC = 0
		site = []
		direct = 'E'
		while posR > -1 and posR < R and (posC > -1) and (posC < C):
			site = [posR, posC]
			change = matrix[posR][posC]
			matrix[posR][posC] = 0
			if change == 1:
				if direct == 'E':
					direct = 'S'
				elif direct == 'S':
					direct = 'W'
				elif direct == 'W':
					direct = 'N'
				elif direct == 'N':
					direct = 'E'
				else:
					pass
			if direct == 'E':
				posC += 1
			elif direct == 'S':
				posR += 1
			elif direct == 'W':
				posC -= 1
			elif direct == 'N':
				posR -= 1
			else:
				pass
		return site


class Solution:

	def endPoints(self, matrix, R, C):
		x = 0
		y = 0
		dire = 0
		ans = []
		while x >= 0 and x < R and (y >= 0) and (y < C):
			ans = [x, y]
			if matrix[x][y] == 1:
				dire = (dire + 1) % 4
				matrix[x][y] = 0
			if dire == 0:
				y = y + 1
			elif dire == 1:
				x = x + 1
			elif dire == 2:
				y = y - 1
			elif dire == 3:
				x = x - 1
		return ans


class Solution:

	def endPoints(self, matrix, R, C):
		(i, j) = (0, 0)
		cur_dir = 'R'
		while True:
			if cur_dir == 'R':
				if matrix[i][j] == 0 and j + 1 < C:
					j = j + 1
				elif matrix[i][j] == 1 and i + 1 < R:
					matrix[i][j] = 0
					i = i + 1
					cur_dir = 'D'
				else:
					break
			elif cur_dir == 'D':
				if matrix[i][j] == 0 and i + 1 < R:
					i = i + 1
				elif matrix[i][j] == 1 and j - 1 >= 0:
					matrix[i][j] = 0
					j = j - 1
					cur_dir = 'L'
				else:
					break
			elif cur_dir == 'L':
				if matrix[i][j] == 0 and j - 1 >= 0:
					j = j - 1
				elif matrix[i][j] == 1 and i - 1 >= 0:
					matrix[i][j] = 0
					i = i - 1
					cur_dir = 'U'
				else:
					break
			elif matrix[i][j] == 0 and i - 1 >= 0:
				i = i - 1
			elif matrix[i][j] == 1 and j + 1 < C:
				matrix[i][j] = 0
				j = j + 1
				cur_dir = 'R'
			else:
				break
		l = [i, j]
		return l


class Solution:
	matrix = []
	R = 0
	C = 0

	def givedirection(self, direction):
		if direction == 'left':
			return 'down'
		elif direction == 'down':
			return 'right'
		elif direction == 'right':
			return 'up'
		else:
			return 'left'

	def giveCoordinates(self, i, j, direction):
		if direction == 'left':
			return [i, j + 1]
		elif direction == 'down':
			return [i + 1, j]
		elif direction == 'right':
			return [i, j - 1]
		else:
			return [i - 1, j]

	def traverse(self, i, j, direction):
		if i >= len(self.matrix) or j >= len(self.matrix[0]) or i < 0 or (j < 0):
			return
		elif self.matrix[i][j] == 0:
			self.R = i
			self.C = j
			return self.traverse(self.giveCoordinates(i, j, direction)[0], self.giveCoordinates(i, j, direction)[1], direction)
		else:
			self.matrix[i][j] = 0
			return self.traverse(i, j, self.givedirection(direction))

	def endPoints(self, matrix, R, C):
		self.matrix = matrix
		self.traverse(0, 0, 'left')
		return [self.R, self.C]


class Solution:

	def endPoints(self, matrix, R, C):
		heading_n = 0
		headings = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		curr = [0, 0]
		while 0 <= curr[0] < R and 0 <= curr[1] < C:
			if matrix[curr[0]][curr[1]] == 1:
				matrix[curr[0]][curr[1]] = 0
				heading_n = (heading_n + 1) % 4
			curr[0] += headings[heading_n][0]
			curr[1] += headings[heading_n][1]
		curr[0] -= headings[heading_n][0]
		curr[1] -= headings[heading_n][1]
		return curr


class Solution:

	def endPoints(self, matrix, R, C):
		st = ['r']
		i = 0
		j = 0
		c = 0
		x = [[0, 0]]
		while (i < len(matrix) and i >= 0) and (j < len(matrix[0]) and j >= 0):
			c += 1
			if matrix[i][j] == 0:
				if st[-1] == 'r':
					j += 1
				elif st[-1] == 'd':
					i += 1
				elif st[-1] == 'u':
					i -= 1
				else:
					j -= 1
			else:
				matrix[i][j] = 0
				if st[-1] == 'r':
					st.append('d')
					i += 1
				elif st[-1] == 'd':
					st.append('l')
					j -= 1
				elif st[-1] == 'u':
					st.append('r')
					j += 1
				else:
					st.append('u')
					i -= 1
			x.append([i, j])
		return x[len(x) - 2]


class Solution:

	def endPoints(self, matrix, R, C):
		directions = ['right', 'down', 'left', 'up']
		row = [0, 1, 0, -1]
		col = [1, 0, -1, 0]
		direction = 0
		rowIndex = 0
		colIndex = 0
		while 0 <= rowIndex < R and 0 <= colIndex < C:
			if matrix[rowIndex][colIndex] == 1:
				matrix[rowIndex][colIndex] = 0
				direction = (direction + 1) % 4
			rowIndex += row[direction]
			colIndex += col[direction]
		if rowIndex > R - 1:
			rowIndex = R - 1
		if rowIndex < 0:
			rowIndex = 0
		if colIndex > C - 1:
			colIndex = C - 1
		if colIndex < 0:
			colIndex = 0
		return (rowIndex, colIndex)


class Solution:

	def endPoints(self, m, r, c):
		cl = 0
		i = j = k = l = 0
		while 0 <= i < r and 0 <= j < c:
			k = i
			l = j
			if m[i][j] == 1:
				m[i][j] = 0
				cl += 1
			if cl % 4 == 0:
				j += 1
			if cl % 4 == 1:
				i += 1
			if cl % 4 == 2:
				j -= 1
			if cl % 4 == 3:
				i -= 1
		return [k, l]


class Solution:
	dir = {'r': 'd', 'd': 'l', 'l': 'u', 'u': 'r'}
	cur = 'r'
	i = 0
	j = 0

	def change_dir(self):
		self.cur = self.dir[self.cur]

	def traverse(self):
		(i, j) = (self.i, self.j)
		if self.cur == 'r':
			j += 1
		elif self.cur == 'd':
			i += 1
		elif self.cur == 'l':
			j -= 1
		elif self.cur == 'u':
			i -= 1
		try:
			self.matrix[i][j]
			if not (i > -1 and j > -1):
				raise Exception('')
			(self.i, self.j) = (i, j)
			return 1
		except Exception as e:
			return 0

	def endPoints(self, matrix, R, C):
		self.matrix = matrix
		while 1:
			if self.matrix[self.i][self.j] == 1:
				self.change_dir()
				self.matrix[self.i][self.j] = 0
			if self.traverse() == 0:
				return (self.i, self.j)
				break


class Solution:

	def endPoints(self, matrix, R, C):
		dir_key = 0
		direction = {0: 'right', 1: 'down', 2: 'left', 3: 'up'}
		i = 0
		j = 0
		while True:
			if i == R or j == C:
				break
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				dir_key = (dir_key + 1) % 4
			if direction[dir_key] == 'right' and j == C - 1:
				return [i, j]
			elif direction[dir_key] == 'down' and i == R - 1:
				return [i, j]
			elif direction[dir_key] == 'left' and j <= 0:
				return [i, 0]
			elif direction[dir_key] == 'up' and i <= 0:
				return [0, j]
			if dir_key == 0:
				j += 1
			elif dir_key == 1:
				i += 1
			elif dir_key == 2:
				j -= 1
			elif dir_key == 3:
				i -= 1


class Solution:

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		direction = 'r'
		direction_change = {'u': 'r', 'r': 'd', 'd': 'l', 'l': 'u'}
		while i in range(0, R) and j in range(0, C):
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				direction = direction_change[direction]
			if direction == 'u':
				i -= 1
			elif direction == 'r':
				j += 1
			elif direction == 'd':
				i += 1
			elif direction == 'l':
				j -= 1
		if i >= R:
			i = R - 1
		elif i < 0:
			i = 0
		if j >= C:
			j = C - 1
		elif j < 0:
			j = 0
		return (i, j)


class Solution:

	def endPoints(self, matrix, R, C):
		curr_dir = 'right'
		dir_map = {'right': 'down', 'down': 'left', 'left': 'top', 'top': 'right'}
		(i, j) = (0, 0)
		while i < R and j < C and (i >= 0) and (j >= 0):
			if matrix[i][j] == 0:
				if curr_dir == 'right':
					j += 1
				elif curr_dir == 'down':
					i += 1
				elif curr_dir == 'left':
					j -= 1
				else:
					i -= 1
				continue
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				curr_dir = dir_map[curr_dir]
		if i > R - 1:
			return (i - 1, j)
		elif i < 0:
			return (i + 1, j)
		elif j > C - 1:
			return (i, j - 1)
		else:
			return (i, j + 1)
		return (i, j)


class Solution:

	def endPoints(self, matrix, R, C):
		isnext = True
		i = j = 0
		previ = prevj = 0
		mr = True
		md = False
		ml = False
		mu = False
		while isnext:
			if j < 0 or j >= C or i < 0 or (i >= R):
				break
			previ = i
			prevj = j
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if mr:
					mr = False
					md = True
					i += 1
				elif md:
					ml = True
					md = False
					j -= 1
				elif ml:
					ml = False
					mu = True
					i -= 1
				elif mu:
					mu = False
					mr = True
					j += 1
			elif mr:
				j += 1
			elif md:
				i += 1
			elif ml:
				j -= 1
			elif mu:
				i -= 1
		return (previ, prevj)


class Solution:

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		dir = 'r'
		mn = {'r': 'd', 'd': 'l', 'l': 'u', 'u': 'r'}
		while True:
			if not matrix[i][j]:
				if dir == 'r':
					if j + 1 == C:
						return (i, j)
					j += 1
				elif dir == 'd':
					if i + 1 == R:
						return (i, j)
					i += 1
				elif dir == 'l':
					if j == 0:
						return (i, j)
					j -= 1
				else:
					if i == 0:
						return (i, j)
					i -= 1
			else:
				matrix[i][j] = 0
				dir = mn[dir]
		return (i, j)


class Solution:

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		dir = 'right'
		mn = {'right': 'down', 'down': 'left', 'left': 'up', 'up': 'right'}
		while True:
			if not matrix[i][j]:
				if dir == 'right':
					if j + 1 == C:
						return (i, j)
					j += 1
				elif dir == 'down':
					if i + 1 == R:
						return (i, j)
					i += 1
				elif dir == 'left':
					if j == 0:
						return (i, j)
					j -= 1
				else:
					if i == 0:
						return (i, j)
					i -= 1
			else:
				matrix[i][j] = 0
				dir = mn[dir]
		return (i, j)


class Solution:

	def endPoints(self, matrix, m, n):
		next_column = 0
		next_row = 0
		direction_pointer = 1
		direction = [['up', -1, 0], ['right', 0, 1], ['down', 1, 0], ['left', 0, -1]]
		while next_row >= 0 and next_row < m and (next_column >= 0) and (next_column < n):
			this_row = next_row
			this_column = next_column
			if matrix[next_row][next_column] == 1:
				matrix[next_row][next_column] = 0
				if direction_pointer == 3:
					direction_pointer = 0
				else:
					direction_pointer = direction_pointer + 1
			next_row += direction[direction_pointer][1]
			next_column += direction[direction_pointer][2]
		return (this_row, this_column)


class Solution:

	def endPoints(self, matrix, R, C):
		direction = 0
		directions = [(0, +1), (+1, 0), (0, -1), (-1, 0)]
		(x, y) = (0, 0)
		while True:
			if matrix[x][y] == 1:
				matrix[x][y] = 0
				direction = (direction + 1) % 4
			x_new = x + directions[direction][0]
			if x_new < R and x_new >= 0:
				x = x_new
			else:
				return (x, y)
			y_new = y + directions[direction][1]
			if y_new < C and y_new >= 0:
				y = y_new
			else:
				return (x, y)


class Solution:

	def endPoints(self, matrix, R, C):
		direction = 1
		r = 0
		c = 0
		while True:
			try:
				ans = [r, c]
				if matrix[r][c] == 1:
					direction += 1
					matrix[r][c] = 0
				if direction > 4:
					direction = 1
				if direction == 1:
					c += 1
				elif direction == 2:
					r += 1
				elif direction == 3:
					c -= 1
				else:
					r -= 1
				if r < 0 or c < 0 or r >= R or (c >= C):
					break
			except IndexError:
				break
		return (ans[0], ans[1])


class Solution:

	def endPoints(self, matrix, R, C):
		(i, j) = (0, 0)
		dir = 'right'
		while 0 <= i < R and 0 <= j < C:
			prev = (i, j)
			if matrix[i][j] == 0:
				if dir == 'right':
					j += 1
				elif dir == 'down':
					i += 1
				elif dir == 'up':
					i -= 1
				else:
					j -= 1
			else:
				matrix[i][j] = 0
				if dir == 'right':
					dir = 'down'
					i += 1
				elif dir == 'down':
					dir = 'left'
					j -= 1
				elif dir == 'up':
					j += 1
					dir = 'right'
				else:
					dir = 'up'
					i -= 1
		return prev


class Solution:

	def endPoints(self, matrix, R, C):
		directions = ['right', 'down', 'left', 'up']
		directionCounter = 0
		row = 0
		col = 0
		while row >= 0 and row < R and (col >= 0) and (col < C):
			currValue = matrix[row][col]
			currRow = row
			currCol = col
			if currValue == 1:
				matrix[row][col] = 0
				directionCounter += 1
			direction = directions[directionCounter % 4]
			if direction == 'right':
				col += 1
			elif direction == 'down':
				row += 1
			elif direction == 'left':
				col -= 1
			else:
				row -= 1
		return (currRow, currCol)


class Solution:

	def endPoints(self, matrix, R, C):
		v = (1, 0)
		(i, j) = (0, 0)
		while True:
			if matrix[i][j] == 1:
				v = self.turn(v)
				matrix[i][j] = 0
			i += v[1]
			j += v[0]
			if i >= R or j >= C or i < 0 or (j < 0):
				return (i - v[1], j - v[0])

	def turn(self, x):
		y = complex(x[0], x[1]) * complex(0, 1)
		return (int(y.real), int(y.imag))


class Solution:

	def endPoints(self, matrix, R, C):
		q = [(0, 0)]
		dr = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		d = 0
		while q:
			(x, y) = q.pop(0)
			if matrix[x][y] == 0:
				d = d
			else:
				d += 1
				matrix[x][y] = 0
			d %= 4
			a = dr[d][0]
			b = dr[d][1]
			(p, k) = (x, y)
			x += a
			y += b
			if x >= R or y >= C or x < 0 or (y < 0):
				return [p, k]
			q.append((x, y))


class Solution:

	def endPoints(self, mat, R, C):
		hm = {}
		right = (0, 1)
		left = (0, -1)
		up = (-1, 0)
		down = (1, 0)
		hm[up] = right
		hm[right] = down
		hm[down] = left
		hm[left] = up
		ans = [(0, 0)]

		def solve(i, j, curr):
			if mat[i][j] == 0:
				ans[0] = (i, j)
				i += curr[0]
				j += curr[1]
				if i >= R or j >= C or i < 0 or (j < 0):
					return
				solve(i, j, curr)
			elif mat[i][j] == 1:
				mat[i][j] = 0
				next = hm[curr]
				ans[0] = (i, j)
				i += next[0]
				j += next[1]
				if i >= R or j >= C or i < 0 or (j < 0):
					return
				solve(i, j, next)
		solve(0, 0, right)
		return ans[0]


class Solution:

	def endPoints(self, matrix, R, C):
		ddp = {'0': [-1, 0], '1': [0, 1], '2': [1, 0], '3': [0, -1]}
		dp = {'0': '1', '1': '2', '2': '3', '3': '0'}
		i = 0
		j = 0
		dirc = '1'
		res = []
		while i >= 0 and i < R and (j < C) and (j >= 0):
			res = [i, j]
			if matrix[i][j] == 1:
				dirc = dp[dirc]
				matrix[i][j] = 0
			(vi, vj) = ddp[dirc]
			i += vi
			j += vj
		return res


class Solution:

	def endPoints(self, matrix, R, C):
		(d, x, y) = (1, 0, 0)
		if matrix[x][y]:
			(matrix[x][y], d) = (0, (d + 1) % 4)
		while True:
			pos = [x, y]
			if d == 0:
				x -= 1
			elif d == 1:
				y += 1
			elif d == 2:
				x += 1
			elif d == 3:
				y -= 1
			if x < 0 or x >= R or y < 0 or (y >= C):
				return pos
			if matrix[x][y]:
				(matrix[x][y], d) = (0, (d + 1) % 4)


class Solution:

	def endPoints(self, arr, R, C):
		i = j = 0
		while True:
			while j < C and arr[i][j] == 0:
				j += 1
			if j == C:
				return [i, C - 1]
			arr[i][j] = 0
			while i < R and arr[i][j] == 0:
				i += 1
			if i == R:
				return [R - 1, j]
			arr[i][j] = 0
			while j >= 0 and arr[i][j] == 0:
				j -= 1
			if j == -1:
				return [i, 0]
			arr[i][j] = 0
			while i >= 0 and arr[i][j] == 0:
				i -= 1
			if i == -1:
				return [0, j]
			arr[i][j] = 0
			continue


class Solution:

	def endPoints(self, matrix, R, C):

		def nextInd(currInd, direction):
			if direction == 'up':
				return (currInd[0] - 1, currInd[1])
			elif direction == 'down':
				return (currInd[0] + 1, currInd[1])
			elif direction == 'left':
				return (currInd[0], currInd[1] - 1)
			else:
				return (currInd[0], currInd[1] + 1)
		direction = 'right'
		currInd = (0, 0)
		while True:
			if matrix[currInd[0]][currInd[1]] == 1:
				if direction == 'up':
					direction = 'right'
				elif direction == 'right':
					direction = 'down'
				elif direction == 'down':
					direction = 'left'
				else:
					direction = 'up'
				matrix[currInd[0]][currInd[1]] = 0
			temp = currInd
			currInd = nextInd(currInd, direction)
			if currInd[0] <= -1 or currInd[0] >= R or currInd[1] <= -1 or (currInd[1] >= C):
				return temp


class Solution:

	def endPoints(self, matrix, R, C):
		i = j = 0
		direction = {'right': 1, 'down': 1, 'left': -1, 'up': -1}
		go = 'right'
		while 1:
			if matrix[i][j] == 0:
				if go == 'right' or go == 'left':
					j += direction[go]
				elif go == 'up' or go == 'down':
					i += direction[go]
			elif matrix[i][j] == 1:
				matrix[i][j] = 0
				if go == 'right':
					go = 'down'
					i += direction[go]
				elif go == 'down':
					go = 'left'
					j += direction[go]
				elif go == 'left':
					go = 'up'
					i += direction[go]
				elif go == 'up':
					go = 'right'
					j += direction[go]
			if j > C - 1:
				return (i, j - 1)
			elif j < 0:
				return (i, j + 1)
			elif i > R - 1:
				return (i - 1, j)
			elif i < 0:
				return (i + 1, j)


class Solution:

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		d = 'r'
		while i < R and j < C:
			if matrix[i][j] == 0:
				if d == 'r':
					if j + 1 >= C:
						return [i, j]
					j += 1
				elif d == 'l':
					if j - 1 < 0:
						return [i, j]
					j -= 1
				elif d == 'u':
					if i - 1 < 0:
						return [i, j]
					i -= 1
				elif d == 'd':
					if i + 1 >= R:
						return [i, j]
					i += 1
			else:
				matrix[i][j] = 0
				if d == 'l':
					if i - 1 < 0:
						return [i, j]
					else:
						d = 'u'
						i -= 1
				elif d == 'r':
					if i + 1 >= R:
						return [i, j]
					else:
						i += 1
						d = 'd'
				elif d == 'd':
					if j - 1 < 0:
						return [i, j]
					else:
						j -= 1
						d = 'l'
				elif d == 'u':
					if j + 1 >= C:
						return [i, j]
					else:
						j += 1
						d = 'r'
		return [i, j]


class Solution:

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		c = 0
		while i < R and j < C and (i >= 0) and (j >= 0):
			if matrix[i][j] == 1:
				c += 1
				c = c % 4
				matrix[i][j] = 0
			if c == 0:
				j += 1
			elif c == 1:
				i += 1
			elif c == 2:
				j -= 1
			elif c == 3:
				i -= 1
		if i >= R:
			i = i - 1
		elif i < 0:
			i = i + 1
		elif j >= C:
			j = j - 1
		elif j < 0:
			j = j + 1
		return [i, j]


class Solution:

	def endPoints(self, matrix, m, n):
		(d, x, y) = (1, 0, 0)
		if matrix[x][y]:
			(matrix[x][y], d) = (0, (d + 1) % 4)
		while True:
			pos = [x, y]
			if d == 0:
				x -= 1
			elif d == 1:
				y += 1
			elif d == 2:
				x += 1
			elif d == 3:
				y -= 1
			if x < 0 or x >= m or y < 0 or (y >= n):
				return pos
			if matrix[x][y]:
				(matrix[x][y], d) = (0, (d + 1) % 4)


class Solution:

	def endPoints(self, matrix, m, n):
		i = 0
		j = 0
		prev = (0, 0)
		direction = 'r'
		while i < m and j < n and (i >= 0) and (j >= 0):
			prev = (i, j)
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if direction == 'r':
					i += 1
					direction = 'd'
				elif direction == 'u':
					j += 1
					direction = 'r'
				elif direction == 'd':
					j -= 1
					direction = 'l'
				elif direction == 'l':
					i -= 1
					direction = 'u'
			elif direction == 'r':
				j += 1
			elif direction == 'u':
				i -= 1
			elif direction == 'd':
				i += 1
			elif direction == 'l':
				j -= 1
		return prev


class Solution:

	def endPoints(self, m, R, C):
		c = 1
		d = {1: [0, 1], 2: [1, 0], 3: [0, -1], 0: [-1, 0]}
		(i, j) = (0, 0)
		(ai, aj) = (i, j)
		while i < R and j < C:
			if m[i][j] == 1:
				m[i][j] = 0
				c += 1
			mv = c % 4
			a = d[mv]
			(ik, jk) = (a[0], a[1])
			if ik + i < 0 or ik + i > R - 1 or jk + j < 0 or (jk + j > C - 1):
				return (i, j)
			i += ik
			j += jk
		return (i, j)


class Solution:

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


class Solution:

	def endPoints(self, matrix, r, c):
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		(i, j) = (0, 0)
		cur_dir = 1
		while i > -1 and i < r and (j > -1) and (j < c):
			cur_i = i
			cur_j = j
			if matrix[cur_i][cur_j] == 0:
				i = i + dx[cur_dir]
				j = j + dy[cur_dir]
			else:
				cur_dir = (cur_dir + 1) % 4
				matrix[i][j] = 0
				i += dx[cur_dir]
				j = j + dy[cur_dir]
		return (cur_i, cur_j)


class Solution:

	def endPoints(self, matrix, R, C):
		(r, c) = (R, C)
		arr = matrix
		dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		curr_dir = 0
		i = j = 0
		while 0 <= i < r and 0 <= j < c:
			if arr[i][j] == 0:
				(dx, dy) = dirs[curr_dir]
				i += dx
				j += dy
			else:
				arr[i][j] = 0
				curr_dir = (curr_dir + 1) % 4
				(dx, dy) = dirs[curr_dir]
			if not (0 <= i < r and 0 <= j < c):
				return (i - dx, j - dy)
		return (-1, -1)


class Solution:

	def endPoints(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		direction = 0
		(i, j) = (0, 0)
		for _ in range(m * n):
			if i < 0 or i >= n or j < 0 or (j >= m):
				if i < 0:
					return (i + 1, j)
				elif i >= n:
					return (i - 1, j)
				elif j < 0:
					return (i, j + 1)
				else:
					return (i, j - 1)
			if matrix[i][j] == 1:
				direction = (direction + 1) % 4
				matrix[i][j] = 0
			if direction == 0:
				j += 1
			elif direction == 1:
				i += 1
			elif direction == 2:
				j -= 1
			else:
				i -= 1
		return (i, j)


class Solution:

	def endPoints(self, matrix, R, C):
		(i, j) = (0, 0)
		(nx, ny) = (0, 1)
		while i < R and j < C:
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if nx == -1 and ny == 0:
					(nx, ny) = (0, 1)
				elif nx == 0 and ny == 1:
					(nx, ny) = (1, 0)
				elif nx == 1 and ny == 0:
					(nx, ny) = (0, -1)
				else:
					(nx, ny) = (-1, 0)
			if i + nx < 0 or i + nx >= R or j + ny < 0 or (j + ny >= C):
				return [i, j]
			i += nx
			j += ny
		return [i, j]


class Solution:

	def endPoints(self, matrix, R, C):
		i = 0
		j = 0
		dirc = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		t = 0
		ans = [0, 0]
		while i != -1 and i != R and (j != -1) and (j != C):
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if t == 3:
					t = 0
				else:
					t += 1
			ans[0] = i
			ans[1] = j
			i += dirc[t][0]
			j += dirc[t][1]
		return ans


class Solution:

	def fun(self, direc):
		dic = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}
		return dic[direc]

	def endPoints(self, matrix, R, C):
		(i, j) = (0, 0)
		dic = {'up': (-1, 0), 'right': (0, 1), 'down': (1, 0), 'left': (0, -1)}
		direc = 'right'
		while True:
			x = matrix[i][j]
			if x == 1:
				matrix[i][j] = 0
				direc = self.fun(direc)
			(a, b) = (dic[direc][0], dic[direc][1])
			if 0 <= i + a < R and 0 <= j + b < C:
				i = i + a
				j = j + b
			else:
				return (i, j)


class Solution:

	def endPoints(self, matrix, R, C):

		def my_move(x, y, dirn):
			moves = {'right': 'down', 'up': 'right', 'down': 'left', 'left': 'up'}
			if matrix[x][y] == 1:
				matrix[x][y] = 0
				dirn = moves[dirn]
			if dirn == 'right':
				y += 1
			elif dirn == 'left':
				y -= 1
			elif dirn == 'down':
				x += 1
			else:
				x -= 1
			return (x, y, dirn)
		dirn = 'right'
		(x, y) = (0, 0)
		while True:
			try:
				if matrix[x][y] == 0 or matrix[x][y] == 1:
					if x < 0 or y < 0:
						raise error
					(result_x, result_y) = (x, y)
					(x, y, dirn) = my_move(x, y, dirn)
			except:
				return (result_x, result_y)


class Solution:

	def endPoints(self, matrix, R, C):
		direction = 0
		x = 0
		y = 0
		prev_x = 0
		prev_y = 0
		while x >= 0 and x < R and (y >= 0) and (y < C):
			prev_x = x
			prev_y = y
			if matrix[x][y] == 1:
				matrix[x][y] = 0
				direction = (direction + 1) % 4
			if direction == 0:
				y += 1
			elif direction == 1:
				x += 1
			elif direction == 2:
				y -= 1
			else:
				x -= 1
		return (prev_x, prev_y)