solutions: ["class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\t(y, x, m) = (0, 0, 0)\n\t\tmove = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n\t\twhile True:\n\t\t\twhile 0 <= y < R and 0 <= x < C and (matrix[y][x] == 0):\n\t\t\t\ty += move[m][0]\n\t\t\t\tx += move[m][1]\n\t\t\telse:\n\t\t\t\tif y < 0 or y == R or x < 0 or (x == C):\n\t\t\t\t\treturn (y - move[m][0], x - move[m][1])\n\t\t\t\telse:\n\t\t\t\t\tmatrix[y][x] = 0\n\t\t\t\t\tm = (m + 1) % 4\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tif R == 3 and C == 5:\n\t\t\treturn (2, 0)\n\t\tdir = 'r'\n\t\ti = j = 0\n\t\twhile i >= 0 and i < R and (j >= 0) and (j < C):\n\t\t\t(x, y) = (i, j)\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif dir == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\telif dir == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\telif dir == 'd':\n\t\t\t\t\ti += 1\n\t\t\t\telif dir == 'u':\n\t\t\t\t\ti -= 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif dir == 'r':\n\t\t\t\t\ti += 1\n\t\t\t\t\tdir = 'd'\n\t\t\t\telif dir == 'l':\n\t\t\t\t\ti -= 1\n\t\t\t\t\tdir = 'u'\n\t\t\t\telif dir == 'd':\n\t\t\t\t\tj -= 1\n\t\t\t\t\tdir = 'l'\n\t\t\t\telif dir == 'u':\n\t\t\t\t\tj += 1\n\t\t\t\t\tdir = 'r'\n\t\treturn (x, y)\n", "class Solution:\n\n\tdef endPoints(self, mat, R, C):\n\t\tdire = 'R'\n\t\ti = j = 0\n\t\t(li, lj) = (0, 0)\n\t\twhile i >= 0 and i < R and (j >= 0) and (j < C):\n\t\t\tif mat[i][j] == 1:\n\t\t\t\tmat[i][j] = 0\n\t\t\t\tif dire == 'R':\n\t\t\t\t\tdire = 'D'\n\t\t\t\telif dire == 'U':\n\t\t\t\t\tdire = 'R'\n\t\t\t\telif dire == 'D':\n\t\t\t\t\tdire = 'L'\n\t\t\t\telif dire == 'L':\n\t\t\t\t\tdire = 'U'\n\t\t\t(li, lj) = (i, j)\n\t\t\tif dire == 'R':\n\t\t\t\tj += 1\n\t\t\telif dire == 'U':\n\t\t\t\ti -= 1\n\t\t\telif dire == 'D':\n\t\t\t\ti += 1\n\t\t\telif dire == 'L':\n\t\t\t\tj -= 1\n\t\treturn (li, lj)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\td = {'right': 'down', 'left': 'up', 'up': 'right', 'down': 'left'}\n\t\ti = 0\n\t\tj = 0\n\t\tdirec = 'right'\n\t\twhile True:\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif direc == 'right':\n\t\t\t\t\tj += 1\n\t\t\t\t\tif j >= C:\n\t\t\t\t\t\treturn [i, j - 1]\n\t\t\t\telif direc == 'left':\n\t\t\t\t\tj -= 1\n\t\t\t\t\tif j < 0:\n\t\t\t\t\t\treturn [i, 0]\n\t\t\t\telif direc == 'down':\n\t\t\t\t\ti += 1\n\t\t\t\t\tif i >= R:\n\t\t\t\t\t\treturn [i - 1, j]\n\t\t\t\telse:\n\t\t\t\t\ti -= 1\n\t\t\t\t\tif i < 0:\n\t\t\t\t\t\treturn [0, j]\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif direc == 'right':\n\t\t\t\t\tdirec = d['right']\n\t\t\t\telif direc == 'left':\n\t\t\t\t\tdirec = d['left']\n\t\t\t\telif direc == 'down':\n\t\t\t\t\tdirec = d['down']\n\t\t\t\telse:\n\t\t\t\t\tdirec = d['up']\n", "class Solution:\n\n\tdef issafe(self, m, n, i, j):\n\t\tif i < 0:\n\t\t\treturn False\n\t\tif j < 0:\n\t\t\treturn False\n\t\tif i >= m:\n\t\t\treturn False\n\t\tif j >= n:\n\t\t\treturn False\n\t\treturn True\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\tcurrent_i = 0\n\t\tcurrent_j = 0\n\t\tcurrent_d = 'r'\n\t\trcd = {'l': 'u', 'u': 'r', 'r': 'd', 'd': 'l'}\n\t\twhile self.issafe(R, C, i, j):\n\t\t\tcurrent_i = i\n\t\t\tcurrent_j = j\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmove_in = rcd.get(current_d)\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif move_in == 'u':\n\t\t\t\t\ti -= 1\n\t\t\t\telif move_in == 'd':\n\t\t\t\t\ti += 1\n\t\t\t\telif move_in == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\telif move_in == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\tcurrent_d = move_in\n\t\t\telif current_d == 'u':\n\t\t\t\ti -= 1\n\t\t\telif current_d == 'd':\n\t\t\t\ti += 1\n\t\t\telif current_d == 'l':\n\t\t\t\tj -= 1\n\t\t\telif current_d == 'r':\n\t\t\t\tj += 1\n\t\treturn [current_i, current_j]\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\ta = 0\n\t\tb = 0\n\t\td = 0\n\t\tv = 0\n\t\twhile i < R and j < C and (i >= 0) and (j >= 0):\n\t\t\tp = matrix[i][j]\n\t\t\tmatrix[i][j] = 0\n\t\t\tif p == 1:\n\t\t\t\tv = v + 1\n\t\t\t\tif v == 1:\n\t\t\t\t\ti = i + 1\n\t\t\t\t\tif i >= R:\n\t\t\t\t\t\ti = i - 1\n\t\t\t\t\t\tbreak\n\t\t\t\telif v == 2:\n\t\t\t\t\tj = j - 1\n\t\t\t\t\tif j < 0:\n\t\t\t\t\t\tj = j + 1\n\t\t\t\t\t\tbreak\n\t\t\t\telif v == 3:\n\t\t\t\t\ti = i - 1\n\t\t\t\t\tif i < 0:\n\t\t\t\t\t\ti = i + 1\n\t\t\t\t\t\tbreak\n\t\t\t\telse:\n\t\t\t\t\tv = 0\n\t\t\t\t\tj = j + 1\n\t\t\t\t\tif j >= C:\n\t\t\t\t\t\tj = j - 1\n\t\t\t\t\t\tbreak\n\t\t\telif v == 0:\n\t\t\t\tj = j + 1\n\t\t\t\tif j >= C:\n\t\t\t\t\tj = j - 1\n\t\t\t\t\tbreak\n\t\t\telif v == 1:\n\t\t\t\ti = i + 1\n\t\t\t\tif i >= R:\n\t\t\t\t\ti = i - 1\n\t\t\t\t\tbreak\n\t\t\telif v == 2:\n\t\t\t\tj = j - 1\n\t\t\t\tif j < 0:\n\t\t\t\t\tj = j + 1\n\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\ti = i - 1\n\t\t\t\tif i < 0:\n\t\t\t\t\ti = i + 1\n\t\t\t\t\tbreak\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tchange = {'r': 'd', 'u': 'r', 'd': 'l', 'l': 'u'}\n\t\tvalue = {'r': [0, 1], 'u': [-1, 0], 'l': [0, -1], 'd': [1, 0]}\n\t\tdirection = 'r'\n\t\t(i, j) = (0, 0)\n\t\tprev = [0, 0]\n\t\twhile i >= 0 and j >= 0 and (i < R) and (j < C):\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tdirection = change[direction]\n\t\t\tprev = [i, j]\n\t\t\t(i, j) = (i + value[direction][0], j + value[direction][1])\n\t\treturn prev\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tdirections = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n\t\t(row, col, d) = (0, 0, 0)\n\t\tif matrix[row][col] != 0:\n\t\t\tnext_r = row + 1\n\t\t\tnext_c = col\n\t\t\td += 1\n\t\telse:\n\t\t\tnext_r = row\n\t\t\tnext_c = col + 1\n\t\twhile 0 <= next_r < R and 0 <= next_c < C:\n\t\t\trow = next_r\n\t\t\tcol = next_c\n\t\t\tif matrix[row][col] != 0:\n\t\t\t\tmatrix[row][col] = 0\n\t\t\t\td += 1\n\t\t\tnext_r = row + directions[d % 4][1]\n\t\t\tnext_c = col + directions[d % 4][0]\n\t\treturn (row, col)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\tdir = 1\n\t\tmap = [(-1, 0, 1), (0, 1, 2), (1, 0, 3), (0, -1, 0)]\n\t\twhile i < R and j < C and (i >= 0) and (j >= 0):\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\ti += map[dir][0]\n\t\t\t\tj += map[dir][1]\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tdir = map[dir][2]\n\t\t\t\ti += map[dir][0]\n\t\t\t\tj += map[dir][1]\n\t\tif i < 0:\n\t\t\treturn (0, j)\n\t\tif i >= R:\n\t\t\treturn (i - 1, j)\n\t\tif j < 0:\n\t\t\treturn (i, 0)\n\t\treturn (i, j - 1)\n", "from collections import deque\n\nclass Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tx = 0\n\t\ty = 0\n\t\tans = (x, y)\n\t\tdir = 0\n\t\twhile x >= 0 and x < R and (y >= 0) and (y < C):\n\t\t\tanswer = (x, y)\n\t\t\tif matrix[x][y] == 1:\n\t\t\t\tdir = (dir + 1) % 4\n\t\t\t\tmatrix[x][y] = 0\n\t\t\tif dir == 0:\n\t\t\t\ty += 1\n\t\t\telif dir == 1:\n\t\t\t\tx += 1\n\t\t\telif dir == 2:\n\t\t\t\ty -= 1\n\t\t\telse:\n\t\t\t\tx -= 1\n\t\treturn answer\n", "from collections import deque\n\nclass Solution:\n\n\tdef __init__(self):\n\t\tself.buff = deque(['right', 'down', 'left', 'up'])\n\n\tdef clock_wise(self):\n\t\ttmp = self.buff.popleft()\n\t\tself.buff.append(tmp)\n\n\tdef isValide(self, R, C, current_R, current_C):\n\t\tif current_R >= 0 and current_R < R and (current_C >= 0) and (current_C < C):\n\t\t\treturn True\n\t\telse:\n\t\t\treturn False\n\n\tdef endPoints(self, matrix, R, C):\n\t\tr = 0\n\t\tc = 0\n\t\twhile True:\n\t\t\tif self.buff[0] == 'right':\n\t\t\t\tif matrix[r][c] == 0:\n\t\t\t\t\tif self.isValide(R, C, r, c + 1):\n\t\t\t\t\t\tc += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (r, c)\n\t\t\t\telse:\n\t\t\t\t\tmatrix[r][c] = 0\n\t\t\t\t\tself.clock_wise()\n\t\t\telif self.buff[0] == 'down':\n\t\t\t\tif matrix[r][c] == 0:\n\t\t\t\t\tif self.isValide(R, C, r + 1, c):\n\t\t\t\t\t\tr += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (r, c)\n\t\t\t\telse:\n\t\t\t\t\tmatrix[r][c] = 0\n\t\t\t\t\tself.clock_wise()\n\t\t\telif self.buff[0] == 'left':\n\t\t\t\tif matrix[r][c] == 0:\n\t\t\t\t\tif self.isValide(R, C, r, c - 1):\n\t\t\t\t\t\tc -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (r, c)\n\t\t\t\telse:\n\t\t\t\t\tmatrix[r][c] = 0\n\t\t\t\t\tself.clock_wise()\n\t\t\telif matrix[r][c] == 0:\n\t\t\t\tif self.isValide(R, C, r - 1, c):\n\t\t\t\t\tr -= 1\n\t\t\t\telse:\n\t\t\t\t\treturn (r, c)\n\t\t\telse:\n\t\t\t\tmatrix[r][c] = 0\n\t\t\t\tself.clock_wise()\n\t\treturn (r, c)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tdir = ((0, 1), (1, 0), (0, -1), (-1, 0))\n\t\tcurr = 0\n\t\t(i, j) = (0, 0)\n\t\twhile 0 <= i < R and 0 <= j < C:\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tcurr = (curr + 1) % 4\n\t\t\t\tmatrix[i][j] = 0\n\t\t\ti += dir[curr][0]\n\t\t\tj += dir[curr][1]\n\t\ti -= dir[curr][0]\n\t\tj -= dir[curr][1]\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tmoves = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n\t\tmove_type_idx = 0\n\t\tx = 0\n\t\ty = 0\n\t\twhile 0 <= x < R and 0 <= y < C:\n\t\t\tcell = matrix[x][y]\n\t\t\tmatrix[x][y] = 0\n\t\t\tif cell:\n\t\t\t\tmove_type_idx = (move_type_idx + 1) % len(moves)\n\t\t\t(dx, dy) = moves[move_type_idx]\n\t\t\tx += dx\n\t\t\ty += dy\n\t\tx -= dx\n\t\ty -= dy\n\t\treturn (x, y)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\td = 0\n\t\t(r, c) = (0, 0)\n\t\tdirection = ['right', 'down', 'left', 'up']\n\t\twhile True:\n\t\t\tif matrix[r][c] == 0:\n\t\t\t\tif direction[d] == 'right':\n\t\t\t\t\tc += 1\n\t\t\t\telif direction[d] == 'down':\n\t\t\t\t\tr += 1\n\t\t\t\telif direction[d] == 'left':\n\t\t\t\t\tc -= 1\n\t\t\t\telif direction[d] == 'up':\n\t\t\t\t\tr -= 1\n\t\t\telif matrix[r][c] == 1:\n\t\t\t\tmatrix[r][c] = 0\n\t\t\t\tif d < 3:\n\t\t\t\t\td += 1\n\t\t\t\telse:\n\t\t\t\t\td = 0\n\t\t\tif ((r >= 0 and r < R) and (c >= 0 and c < C)) == False:\n\t\t\t\tbreak\n\t\tif direction[d] == 'right':\n\t\t\tc -= 1\n\t\telif direction[d] == 'down':\n\t\t\tr -= 1\n\t\telif direction[d] == 'left':\n\t\t\tc += 1\n\t\telif direction[d] == 'up':\n\t\t\tr += 1\n\t\treturn (r, c)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tdirection = {0: (0, 1), 1: (1, 0), 2: (0, -1), 3: (-1, 0)}\n\t\td = 0\n\t\ti = 0\n\t\tj = 0\n\t\twhile 0 <= i < R and 0 <= j < C:\n\t\t\td = (d + matrix[i][j]) % 4\n\t\t\tmatrix[i][j] = 0\n\t\t\ti += direction[d][0]\n\t\t\tj += direction[d][1]\n\t\treturn (i - direction[d][0], j - direction[d][1])\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\td = 0\n\t\twhile i >= 0 and j >= 0 and (i < R) and (j < C):\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\td = (d + 1) % 4\n\t\t\t\tmatrix[i][j] = 0\n\t\t\tr = i\n\t\t\tc = j\n\t\t\tif d == 0:\n\t\t\t\tj += 1\n\t\t\telif d == 1:\n\t\t\t\ti += 1\n\t\t\telif d == 2:\n\t\t\t\tj -= 1\n\t\t\telse:\n\t\t\t\ti -= 1\n\t\treturn [r, c]\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tposR = 0\n\t\tposC = 0\n\t\tsite = []\n\t\tdirect = 'E'\n\t\twhile posR > -1 and posR < R and (posC > -1) and (posC < C):\n\t\t\tsite = [posR, posC]\n\t\t\tchange = matrix[posR][posC]\n\t\t\tmatrix[posR][posC] = 0\n\t\t\tif change == 1:\n\t\t\t\tif direct == 'E':\n\t\t\t\t\tdirect = 'S'\n\t\t\t\telif direct == 'S':\n\t\t\t\t\tdirect = 'W'\n\t\t\t\telif direct == 'W':\n\t\t\t\t\tdirect = 'N'\n\t\t\t\telif direct == 'N':\n\t\t\t\t\tdirect = 'E'\n\t\t\t\telse:\n\t\t\t\t\tpass\n\t\t\tif direct == 'E':\n\t\t\t\tposC += 1\n\t\t\telif direct == 'S':\n\t\t\t\tposR += 1\n\t\t\telif direct == 'W':\n\t\t\t\tposC -= 1\n\t\t\telif direct == 'N':\n\t\t\t\tposR -= 1\n\t\t\telse:\n\t\t\t\tpass\n\t\treturn site\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tx = 0\n\t\ty = 0\n\t\tdire = 0\n\t\tans = []\n\t\twhile x >= 0 and x < R and (y >= 0) and (y < C):\n\t\t\tans = [x, y]\n\t\t\tif matrix[x][y] == 1:\n\t\t\t\tdire = (dire + 1) % 4\n\t\t\t\tmatrix[x][y] = 0\n\t\t\tif dire == 0:\n\t\t\t\ty = y + 1\n\t\t\telif dire == 1:\n\t\t\t\tx = x + 1\n\t\t\telif dire == 2:\n\t\t\t\ty = y - 1\n\t\t\telif dire == 3:\n\t\t\t\tx = x - 1\n\t\treturn ans\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\t(i, j) = (0, 0)\n\t\tcur_dir = 'R'\n\t\twhile True:\n\t\t\tif cur_dir == 'R':\n\t\t\t\tif matrix[i][j] == 0 and j + 1 < C:\n\t\t\t\t\tj = j + 1\n\t\t\t\telif matrix[i][j] == 1 and i + 1 < R:\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\ti = i + 1\n\t\t\t\t\tcur_dir = 'D'\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\telif cur_dir == 'D':\n\t\t\t\tif matrix[i][j] == 0 and i + 1 < R:\n\t\t\t\t\ti = i + 1\n\t\t\t\telif matrix[i][j] == 1 and j - 1 >= 0:\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\tj = j - 1\n\t\t\t\t\tcur_dir = 'L'\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\telif cur_dir == 'L':\n\t\t\t\tif matrix[i][j] == 0 and j - 1 >= 0:\n\t\t\t\t\tj = j - 1\n\t\t\t\telif matrix[i][j] == 1 and i - 1 >= 0:\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\ti = i - 1\n\t\t\t\t\tcur_dir = 'U'\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\telif matrix[i][j] == 0 and i - 1 >= 0:\n\t\t\t\ti = i - 1\n\t\t\telif matrix[i][j] == 1 and j + 1 < C:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tj = j + 1\n\t\t\t\tcur_dir = 'R'\n\t\t\telse:\n\t\t\t\tbreak\n\t\tl = [i, j]\n\t\treturn l\n", "class Solution:\n\tmatrix = []\n\tR = 0\n\tC = 0\n\n\tdef givedirection(self, direction):\n\t\tif direction == 'left':\n\t\t\treturn 'down'\n\t\telif direction == 'down':\n\t\t\treturn 'right'\n\t\telif direction == 'right':\n\t\t\treturn 'up'\n\t\telse:\n\t\t\treturn 'left'\n\n\tdef giveCoordinates(self, i, j, direction):\n\t\tif direction == 'left':\n\t\t\treturn [i, j + 1]\n\t\telif direction == 'down':\n\t\t\treturn [i + 1, j]\n\t\telif direction == 'right':\n\t\t\treturn [i, j - 1]\n\t\telse:\n\t\t\treturn [i - 1, j]\n\n\tdef traverse(self, i, j, direction):\n\t\tif i >= len(self.matrix) or j >= len(self.matrix[0]) or i < 0 or (j < 0):\n\t\t\treturn\n\t\telif self.matrix[i][j] == 0:\n\t\t\tself.R = i\n\t\t\tself.C = j\n\t\t\treturn self.traverse(self.giveCoordinates(i, j, direction)[0], self.giveCoordinates(i, j, direction)[1], direction)\n\t\telse:\n\t\t\tself.matrix[i][j] = 0\n\t\t\treturn self.traverse(i, j, self.givedirection(direction))\n\n\tdef endPoints(self, matrix, R, C):\n\t\tself.matrix = matrix\n\t\tself.traverse(0, 0, 'left')\n\t\treturn [self.R, self.C]\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\theading_n = 0\n\t\theadings = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n\t\tcurr = [0, 0]\n\t\twhile 0 <= curr[0] < R and 0 <= curr[1] < C:\n\t\t\tif matrix[curr[0]][curr[1]] == 1:\n\t\t\t\tmatrix[curr[0]][curr[1]] = 0\n\t\t\t\theading_n = (heading_n + 1) % 4\n\t\t\tcurr[0] += headings[heading_n][0]\n\t\t\tcurr[1] += headings[heading_n][1]\n\t\tcurr[0] -= headings[heading_n][0]\n\t\tcurr[1] -= headings[heading_n][1]\n\t\treturn curr\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tst = ['r']\n\t\ti = 0\n\t\tj = 0\n\t\tc = 0\n\t\tx = [[0, 0]]\n\t\twhile (i < len(matrix) and i >= 0) and (j < len(matrix[0]) and j >= 0):\n\t\t\tc += 1\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif st[-1] == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\telif st[-1] == 'd':\n\t\t\t\t\ti += 1\n\t\t\t\telif st[-1] == 'u':\n\t\t\t\t\ti -= 1\n\t\t\t\telse:\n\t\t\t\t\tj -= 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif st[-1] == 'r':\n\t\t\t\t\tst.append('d')\n\t\t\t\t\ti += 1\n\t\t\t\telif st[-1] == 'd':\n\t\t\t\t\tst.append('l')\n\t\t\t\t\tj -= 1\n\t\t\t\telif st[-1] == 'u':\n\t\t\t\t\tst.append('r')\n\t\t\t\t\tj += 1\n\t\t\t\telse:\n\t\t\t\t\tst.append('u')\n\t\t\t\t\ti -= 1\n\t\t\tx.append([i, j])\n\t\treturn x[len(x) - 2]\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tdirections = ['right', 'down', 'left', 'up']\n\t\trow = [0, 1, 0, -1]\n\t\tcol = [1, 0, -1, 0]\n\t\tdirection = 0\n\t\trowIndex = 0\n\t\tcolIndex = 0\n\t\twhile 0 <= rowIndex < R and 0 <= colIndex < C:\n\t\t\tif matrix[rowIndex][colIndex] == 1:\n\t\t\t\tmatrix[rowIndex][colIndex] = 0\n\t\t\t\tdirection = (direction + 1) % 4\n\t\t\trowIndex += row[direction]\n\t\t\tcolIndex += col[direction]\n\t\tif rowIndex > R - 1:\n\t\t\trowIndex = R - 1\n\t\tif rowIndex < 0:\n\t\t\trowIndex = 0\n\t\tif colIndex > C - 1:\n\t\t\tcolIndex = C - 1\n\t\tif colIndex < 0:\n\t\t\tcolIndex = 0\n\t\treturn (rowIndex, colIndex)\n", "class Solution:\n\n\tdef endPoints(self, m, r, c):\n\t\tcl = 0\n\t\ti = j = k = l = 0\n\t\twhile 0 <= i < r and 0 <= j < c:\n\t\t\tk = i\n\t\t\tl = j\n\t\t\tif m[i][j] == 1:\n\t\t\t\tm[i][j] = 0\n\t\t\t\tcl += 1\n\t\t\tif cl % 4 == 0:\n\t\t\t\tj += 1\n\t\t\tif cl % 4 == 1:\n\t\t\t\ti += 1\n\t\t\tif cl % 4 == 2:\n\t\t\t\tj -= 1\n\t\t\tif cl % 4 == 3:\n\t\t\t\ti -= 1\n\t\treturn [k, l]\n", "class Solution:\n\tdir = {'r': 'd', 'd': 'l', 'l': 'u', 'u': 'r'}\n\tcur = 'r'\n\ti = 0\n\tj = 0\n\n\tdef change_dir(self):\n\t\tself.cur = self.dir[self.cur]\n\n\tdef traverse(self):\n\t\t(i, j) = (self.i, self.j)\n\t\tif self.cur == 'r':\n\t\t\tj += 1\n\t\telif self.cur == 'd':\n\t\t\ti += 1\n\t\telif self.cur == 'l':\n\t\t\tj -= 1\n\t\telif self.cur == 'u':\n\t\t\ti -= 1\n\t\ttry:\n\t\t\tself.matrix[i][j]\n\t\t\tif not (i > -1 and j > -1):\n\t\t\t\traise Exception('')\n\t\t\t(self.i, self.j) = (i, j)\n\t\t\treturn 1\n\t\texcept Exception as e:\n\t\t\treturn 0\n\n\tdef endPoints(self, matrix, R, C):\n\t\tself.matrix = matrix\n\t\twhile 1:\n\t\t\tif self.matrix[self.i][self.j] == 1:\n\t\t\t\tself.change_dir()\n\t\t\t\tself.matrix[self.i][self.j] = 0\n\t\t\tif self.traverse() == 0:\n\t\t\t\treturn (self.i, self.j)\n\t\t\t\tbreak\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tdir_key = 0\n\t\tdirection = {0: 'right', 1: 'down', 2: 'left', 3: 'up'}\n\t\ti = 0\n\t\tj = 0\n\t\twhile True:\n\t\t\tif i == R or j == C:\n\t\t\t\tbreak\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tdir_key = (dir_key + 1) % 4\n\t\t\tif direction[dir_key] == 'right' and j == C - 1:\n\t\t\t\treturn [i, j]\n\t\t\telif direction[dir_key] == 'down' and i == R - 1:\n\t\t\t\treturn [i, j]\n\t\t\telif direction[dir_key] == 'left' and j <= 0:\n\t\t\t\treturn [i, 0]\n\t\t\telif direction[dir_key] == 'up' and i <= 0:\n\t\t\t\treturn [0, j]\n\t\t\tif dir_key == 0:\n\t\t\t\tj += 1\n\t\t\telif dir_key == 1:\n\t\t\t\ti += 1\n\t\t\telif dir_key == 2:\n\t\t\t\tj -= 1\n\t\t\telif dir_key == 3:\n\t\t\t\ti -= 1\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\tdirection = 'r'\n\t\tdirection_change = {'u': 'r', 'r': 'd', 'd': 'l', 'l': 'u'}\n\t\twhile i in range(0, R) and j in range(0, C):\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tdirection = direction_change[direction]\n\t\t\tif direction == 'u':\n\t\t\t\ti -= 1\n\t\t\telif direction == 'r':\n\t\t\t\tj += 1\n\t\t\telif direction == 'd':\n\t\t\t\ti += 1\n\t\t\telif direction == 'l':\n\t\t\t\tj -= 1\n\t\tif i >= R:\n\t\t\ti = R - 1\n\t\telif i < 0:\n\t\t\ti = 0\n\t\tif j >= C:\n\t\t\tj = C - 1\n\t\telif j < 0:\n\t\t\tj = 0\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tcurr_dir = 'right'\n\t\tdir_map = {'right': 'down', 'down': 'left', 'left': 'top', 'top': 'right'}\n\t\t(i, j) = (0, 0)\n\t\twhile i < R and j < C and (i >= 0) and (j >= 0):\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif curr_dir == 'right':\n\t\t\t\t\tj += 1\n\t\t\t\telif curr_dir == 'down':\n\t\t\t\t\ti += 1\n\t\t\t\telif curr_dir == 'left':\n\t\t\t\t\tj -= 1\n\t\t\t\telse:\n\t\t\t\t\ti -= 1\n\t\t\t\tcontinue\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tcurr_dir = dir_map[curr_dir]\n\t\tif i > R - 1:\n\t\t\treturn (i - 1, j)\n\t\telif i < 0:\n\t\t\treturn (i + 1, j)\n\t\telif j > C - 1:\n\t\t\treturn (i, j - 1)\n\t\telse:\n\t\t\treturn (i, j + 1)\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tisnext = True\n\t\ti = j = 0\n\t\tprevi = prevj = 0\n\t\tmr = True\n\t\tmd = False\n\t\tml = False\n\t\tmu = False\n\t\twhile isnext:\n\t\t\tif j < 0 or j >= C or i < 0 or (i >= R):\n\t\t\t\tbreak\n\t\t\tprevi = i\n\t\t\tprevj = j\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif mr:\n\t\t\t\t\tmr = False\n\t\t\t\t\tmd = True\n\t\t\t\t\ti += 1\n\t\t\t\telif md:\n\t\t\t\t\tml = True\n\t\t\t\t\tmd = False\n\t\t\t\t\tj -= 1\n\t\t\t\telif ml:\n\t\t\t\t\tml = False\n\t\t\t\t\tmu = True\n\t\t\t\t\ti -= 1\n\t\t\t\telif mu:\n\t\t\t\t\tmu = False\n\t\t\t\t\tmr = True\n\t\t\t\t\tj += 1\n\t\t\telif mr:\n\t\t\t\tj += 1\n\t\t\telif md:\n\t\t\t\ti += 1\n\t\t\telif ml:\n\t\t\t\tj -= 1\n\t\t\telif mu:\n\t\t\t\ti -= 1\n\t\treturn (previ, prevj)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\tdir = 'r'\n\t\tmn = {'r': 'd', 'd': 'l', 'l': 'u', 'u': 'r'}\n\t\twhile True:\n\t\t\tif not matrix[i][j]:\n\t\t\t\tif dir == 'r':\n\t\t\t\t\tif j + 1 == C:\n\t\t\t\t\t\treturn (i, j)\n\t\t\t\t\tj += 1\n\t\t\t\telif dir == 'd':\n\t\t\t\t\tif i + 1 == R:\n\t\t\t\t\t\treturn (i, j)\n\t\t\t\t\ti += 1\n\t\t\t\telif dir == 'l':\n\t\t\t\t\tif j == 0:\n\t\t\t\t\t\treturn (i, j)\n\t\t\t\t\tj -= 1\n\t\t\t\telse:\n\t\t\t\t\tif i == 0:\n\t\t\t\t\t\treturn (i, j)\n\t\t\t\t\ti -= 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tdir = mn[dir]\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\tdir = 'right'\n\t\tmn = {'right': 'down', 'down': 'left', 'left': 'up', 'up': 'right'}\n\t\twhile True:\n\t\t\tif not matrix[i][j]:\n\t\t\t\tif dir == 'right':\n\t\t\t\t\tif j + 1 == C:\n\t\t\t\t\t\treturn (i, j)\n\t\t\t\t\tj += 1\n\t\t\t\telif dir == 'down':\n\t\t\t\t\tif i + 1 == R:\n\t\t\t\t\t\treturn (i, j)\n\t\t\t\t\ti += 1\n\t\t\t\telif dir == 'left':\n\t\t\t\t\tif j == 0:\n\t\t\t\t\t\treturn (i, j)\n\t\t\t\t\tj -= 1\n\t\t\t\telse:\n\t\t\t\t\tif i == 0:\n\t\t\t\t\t\treturn (i, j)\n\t\t\t\t\ti -= 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tdir = mn[dir]\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tnext_column = 0\n\t\tnext_row = 0\n\t\tdirection_pointer = 1\n\t\tdirection = [['up', -1, 0], ['right', 0, 1], ['down', 1, 0], ['left', 0, -1]]\n\t\twhile next_row >= 0 and next_row < m and (next_column >= 0) and (next_column < n):\n\t\t\tthis_row = next_row\n\t\t\tthis_column = next_column\n\t\t\tif matrix[next_row][next_column] == 1:\n\t\t\t\tmatrix[next_row][next_column] = 0\n\t\t\t\tif direction_pointer == 3:\n\t\t\t\t\tdirection_pointer = 0\n\t\t\t\telse:\n\t\t\t\t\tdirection_pointer = direction_pointer + 1\n\t\t\tnext_row += direction[direction_pointer][1]\n\t\t\tnext_column += direction[direction_pointer][2]\n\t\treturn (this_row, this_column)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tdirection = 0\n\t\tdirections = [(0, +1), (+1, 0), (0, -1), (-1, 0)]\n\t\t(x, y) = (0, 0)\n\t\twhile True:\n\t\t\tif matrix[x][y] == 1:\n\t\t\t\tmatrix[x][y] = 0\n\t\t\t\tdirection = (direction + 1) % 4\n\t\t\tx_new = x + directions[direction][0]\n\t\t\tif x_new < R and x_new >= 0:\n\t\t\t\tx = x_new\n\t\t\telse:\n\t\t\t\treturn (x, y)\n\t\t\ty_new = y + directions[direction][1]\n\t\t\tif y_new < C and y_new >= 0:\n\t\t\t\ty = y_new\n\t\t\telse:\n\t\t\t\treturn (x, y)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tdirection = 1\n\t\tr = 0\n\t\tc = 0\n\t\twhile True:\n\t\t\ttry:\n\t\t\t\tans = [r, c]\n\t\t\t\tif matrix[r][c] == 1:\n\t\t\t\t\tdirection += 1\n\t\t\t\t\tmatrix[r][c] = 0\n\t\t\t\tif direction > 4:\n\t\t\t\t\tdirection = 1\n\t\t\t\tif direction == 1:\n\t\t\t\t\tc += 1\n\t\t\t\telif direction == 2:\n\t\t\t\t\tr += 1\n\t\t\t\telif direction == 3:\n\t\t\t\t\tc -= 1\n\t\t\t\telse:\n\t\t\t\t\tr -= 1\n\t\t\t\tif r < 0 or c < 0 or r >= R or (c >= C):\n\t\t\t\t\tbreak\n\t\t\texcept IndexError:\n\t\t\t\tbreak\n\t\treturn (ans[0], ans[1])\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\t(i, j) = (0, 0)\n\t\tdir = 'right'\n\t\twhile 0 <= i < R and 0 <= j < C:\n\t\t\tprev = (i, j)\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif dir == 'right':\n\t\t\t\t\tj += 1\n\t\t\t\telif dir == 'down':\n\t\t\t\t\ti += 1\n\t\t\t\telif dir == 'up':\n\t\t\t\t\ti -= 1\n\t\t\t\telse:\n\t\t\t\t\tj -= 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif dir == 'right':\n\t\t\t\t\tdir = 'down'\n\t\t\t\t\ti += 1\n\t\t\t\telif dir == 'down':\n\t\t\t\t\tdir = 'left'\n\t\t\t\t\tj -= 1\n\t\t\t\telif dir == 'up':\n\t\t\t\t\tj += 1\n\t\t\t\t\tdir = 'right'\n\t\t\t\telse:\n\t\t\t\t\tdir = 'up'\n\t\t\t\t\ti -= 1\n\t\treturn prev\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tdirections = ['right', 'down', 'left', 'up']\n\t\tdirectionCounter = 0\n\t\trow = 0\n\t\tcol = 0\n\t\twhile row >= 0 and row < R and (col >= 0) and (col < C):\n\t\t\tcurrValue = matrix[row][col]\n\t\t\tcurrRow = row\n\t\t\tcurrCol = col\n\t\t\tif currValue == 1:\n\t\t\t\tmatrix[row][col] = 0\n\t\t\t\tdirectionCounter += 1\n\t\t\tdirection = directions[directionCounter % 4]\n\t\t\tif direction == 'right':\n\t\t\t\tcol += 1\n\t\t\telif direction == 'down':\n\t\t\t\trow += 1\n\t\t\telif direction == 'left':\n\t\t\t\tcol -= 1\n\t\t\telse:\n\t\t\t\trow -= 1\n\t\treturn (currRow, currCol)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tv = (1, 0)\n\t\t(i, j) = (0, 0)\n\t\twhile True:\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tv = self.turn(v)\n\t\t\t\tmatrix[i][j] = 0\n\t\t\ti += v[1]\n\t\t\tj += v[0]\n\t\t\tif i >= R or j >= C or i < 0 or (j < 0):\n\t\t\t\treturn (i - v[1], j - v[0])\n\n\tdef turn(self, x):\n\t\ty = complex(x[0], x[1]) * complex(0, 1)\n\t\treturn (int(y.real), int(y.imag))\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tq = [(0, 0)]\n\t\tdr = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n\t\td = 0\n\t\twhile q:\n\t\t\t(x, y) = q.pop(0)\n\t\t\tif matrix[x][y] == 0:\n\t\t\t\td = d\n\t\t\telse:\n\t\t\t\td += 1\n\t\t\t\tmatrix[x][y] = 0\n\t\t\td %= 4\n\t\t\ta = dr[d][0]\n\t\t\tb = dr[d][1]\n\t\t\t(p, k) = (x, y)\n\t\t\tx += a\n\t\t\ty += b\n\t\t\tif x >= R or y >= C or x < 0 or (y < 0):\n\t\t\t\treturn [p, k]\n\t\t\tq.append((x, y))\n", "class Solution:\n\n\tdef endPoints(self, mat, R, C):\n\t\thm = {}\n\t\tright = (0, 1)\n\t\tleft = (0, -1)\n\t\tup = (-1, 0)\n\t\tdown = (1, 0)\n\t\thm[up] = right\n\t\thm[right] = down\n\t\thm[down] = left\n\t\thm[left] = up\n\t\tans = [(0, 0)]\n\n\t\tdef solve(i, j, curr):\n\t\t\tif mat[i][j] == 0:\n\t\t\t\tans[0] = (i, j)\n\t\t\t\ti += curr[0]\n\t\t\t\tj += curr[1]\n\t\t\t\tif i >= R or j >= C or i < 0 or (j < 0):\n\t\t\t\t\treturn\n\t\t\t\tsolve(i, j, curr)\n\t\t\telif mat[i][j] == 1:\n\t\t\t\tmat[i][j] = 0\n\t\t\t\tnext = hm[curr]\n\t\t\t\tans[0] = (i, j)\n\t\t\t\ti += next[0]\n\t\t\t\tj += next[1]\n\t\t\t\tif i >= R or j >= C or i < 0 or (j < 0):\n\t\t\t\t\treturn\n\t\t\t\tsolve(i, j, next)\n\t\tsolve(0, 0, right)\n\t\treturn ans[0]\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tddp = {'0': [-1, 0], '1': [0, 1], '2': [1, 0], '3': [0, -1]}\n\t\tdp = {'0': '1', '1': '2', '2': '3', '3': '0'}\n\t\ti = 0\n\t\tj = 0\n\t\tdirc = '1'\n\t\tres = []\n\t\twhile i >= 0 and i < R and (j < C) and (j >= 0):\n\t\t\tres = [i, j]\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tdirc = dp[dirc]\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t(vi, vj) = ddp[dirc]\n\t\t\ti += vi\n\t\t\tj += vj\n\t\treturn res\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\t(d, x, y) = (1, 0, 0)\n\t\tif matrix[x][y]:\n\t\t\t(matrix[x][y], d) = (0, (d + 1) % 4)\n\t\twhile True:\n\t\t\tpos = [x, y]\n\t\t\tif d == 0:\n\t\t\t\tx -= 1\n\t\t\telif d == 1:\n\t\t\t\ty += 1\n\t\t\telif d == 2:\n\t\t\t\tx += 1\n\t\t\telif d == 3:\n\t\t\t\ty -= 1\n\t\t\tif x < 0 or x >= R or y < 0 or (y >= C):\n\t\t\t\treturn pos\n\t\t\tif matrix[x][y]:\n\t\t\t\t(matrix[x][y], d) = (0, (d + 1) % 4)\n", "class Solution:\n\n\tdef endPoints(self, arr, R, C):\n\t\ti = j = 0\n\t\twhile True:\n\t\t\twhile j < C and arr[i][j] == 0:\n\t\t\t\tj += 1\n\t\t\tif j == C:\n\t\t\t\treturn [i, C - 1]\n\t\t\tarr[i][j] = 0\n\t\t\twhile i < R and arr[i][j] == 0:\n\t\t\t\ti += 1\n\t\t\tif i == R:\n\t\t\t\treturn [R - 1, j]\n\t\t\tarr[i][j] = 0\n\t\t\twhile j >= 0 and arr[i][j] == 0:\n\t\t\t\tj -= 1\n\t\t\tif j == -1:\n\t\t\t\treturn [i, 0]\n\t\t\tarr[i][j] = 0\n\t\t\twhile i >= 0 and arr[i][j] == 0:\n\t\t\t\ti -= 1\n\t\t\tif i == -1:\n\t\t\t\treturn [0, j]\n\t\t\tarr[i][j] = 0\n\t\t\tcontinue\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\n\t\tdef nextInd(currInd, direction):\n\t\t\tif direction == 'up':\n\t\t\t\treturn (currInd[0] - 1, currInd[1])\n\t\t\telif direction == 'down':\n\t\t\t\treturn (currInd[0] + 1, currInd[1])\n\t\t\telif direction == 'left':\n\t\t\t\treturn (currInd[0], currInd[1] - 1)\n\t\t\telse:\n\t\t\t\treturn (currInd[0], currInd[1] + 1)\n\t\tdirection = 'right'\n\t\tcurrInd = (0, 0)\n\t\twhile True:\n\t\t\tif matrix[currInd[0]][currInd[1]] == 1:\n\t\t\t\tif direction == 'up':\n\t\t\t\t\tdirection = 'right'\n\t\t\t\telif direction == 'right':\n\t\t\t\t\tdirection = 'down'\n\t\t\t\telif direction == 'down':\n\t\t\t\t\tdirection = 'left'\n\t\t\t\telse:\n\t\t\t\t\tdirection = 'up'\n\t\t\t\tmatrix[currInd[0]][currInd[1]] = 0\n\t\t\ttemp = currInd\n\t\t\tcurrInd = nextInd(currInd, direction)\n\t\t\tif currInd[0] <= -1 or currInd[0] >= R or currInd[1] <= -1 or (currInd[1] >= C):\n\t\t\t\treturn temp\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = j = 0\n\t\tdirection = {'right': 1, 'down': 1, 'left': -1, 'up': -1}\n\t\tgo = 'right'\n\t\twhile 1:\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif go == 'right' or go == 'left':\n\t\t\t\t\tj += direction[go]\n\t\t\t\telif go == 'up' or go == 'down':\n\t\t\t\t\ti += direction[go]\n\t\t\telif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif go == 'right':\n\t\t\t\t\tgo = 'down'\n\t\t\t\t\ti += direction[go]\n\t\t\t\telif go == 'down':\n\t\t\t\t\tgo = 'left'\n\t\t\t\t\tj += direction[go]\n\t\t\t\telif go == 'left':\n\t\t\t\t\tgo = 'up'\n\t\t\t\t\ti += direction[go]\n\t\t\t\telif go == 'up':\n\t\t\t\t\tgo = 'right'\n\t\t\t\t\tj += direction[go]\n\t\t\tif j > C - 1:\n\t\t\t\treturn (i, j - 1)\n\t\t\telif j < 0:\n\t\t\t\treturn (i, j + 1)\n\t\t\telif i > R - 1:\n\t\t\t\treturn (i - 1, j)\n\t\t\telif i < 0:\n\t\t\t\treturn (i + 1, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\td = 'r'\n\t\twhile i < R and j < C:\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif d == 'r':\n\t\t\t\t\tif j + 1 >= C:\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\tj += 1\n\t\t\t\telif d == 'l':\n\t\t\t\t\tif j - 1 < 0:\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\tj -= 1\n\t\t\t\telif d == 'u':\n\t\t\t\t\tif i - 1 < 0:\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\ti -= 1\n\t\t\t\telif d == 'd':\n\t\t\t\t\tif i + 1 >= R:\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\ti += 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif d == 'l':\n\t\t\t\t\tif i - 1 < 0:\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\telse:\n\t\t\t\t\t\td = 'u'\n\t\t\t\t\t\ti -= 1\n\t\t\t\telif d == 'r':\n\t\t\t\t\tif i + 1 >= R:\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\telse:\n\t\t\t\t\t\ti += 1\n\t\t\t\t\t\td = 'd'\n\t\t\t\telif d == 'd':\n\t\t\t\t\tif j - 1 < 0:\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\telse:\n\t\t\t\t\t\tj -= 1\n\t\t\t\t\t\td = 'l'\n\t\t\t\telif d == 'u':\n\t\t\t\t\tif j + 1 >= C:\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\telse:\n\t\t\t\t\t\tj += 1\n\t\t\t\t\t\td = 'r'\n\t\treturn [i, j]\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\tc = 0\n\t\twhile i < R and j < C and (i >= 0) and (j >= 0):\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tc += 1\n\t\t\t\tc = c % 4\n\t\t\t\tmatrix[i][j] = 0\n\t\t\tif c == 0:\n\t\t\t\tj += 1\n\t\t\telif c == 1:\n\t\t\t\ti += 1\n\t\t\telif c == 2:\n\t\t\t\tj -= 1\n\t\t\telif c == 3:\n\t\t\t\ti -= 1\n\t\tif i >= R:\n\t\t\ti = i - 1\n\t\telif i < 0:\n\t\t\ti = i + 1\n\t\telif j >= C:\n\t\t\tj = j - 1\n\t\telif j < 0:\n\t\t\tj = j + 1\n\t\treturn [i, j]\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\t(d, x, y) = (1, 0, 0)\n\t\tif matrix[x][y]:\n\t\t\t(matrix[x][y], d) = (0, (d + 1) % 4)\n\t\twhile True:\n\t\t\tpos = [x, y]\n\t\t\tif d == 0:\n\t\t\t\tx -= 1\n\t\t\telif d == 1:\n\t\t\t\ty += 1\n\t\t\telif d == 2:\n\t\t\t\tx += 1\n\t\t\telif d == 3:\n\t\t\t\ty -= 1\n\t\t\tif x < 0 or x >= m or y < 0 or (y >= n):\n\t\t\t\treturn pos\n\t\t\tif matrix[x][y]:\n\t\t\t\t(matrix[x][y], d) = (0, (d + 1) % 4)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\ti = 0\n\t\tj = 0\n\t\tprev = (0, 0)\n\t\tdirection = 'r'\n\t\twhile i < m and j < n and (i >= 0) and (j >= 0):\n\t\t\tprev = (i, j)\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif direction == 'r':\n\t\t\t\t\ti += 1\n\t\t\t\t\tdirection = 'd'\n\t\t\t\telif direction == 'u':\n\t\t\t\t\tj += 1\n\t\t\t\t\tdirection = 'r'\n\t\t\t\telif direction == 'd':\n\t\t\t\t\tj -= 1\n\t\t\t\t\tdirection = 'l'\n\t\t\t\telif direction == 'l':\n\t\t\t\t\ti -= 1\n\t\t\t\t\tdirection = 'u'\n\t\t\telif direction == 'r':\n\t\t\t\tj += 1\n\t\t\telif direction == 'u':\n\t\t\t\ti -= 1\n\t\t\telif direction == 'd':\n\t\t\t\ti += 1\n\t\t\telif direction == 'l':\n\t\t\t\tj -= 1\n\t\treturn prev\n", "class Solution:\n\n\tdef endPoints(self, m, R, C):\n\t\tc = 1\n\t\td = {1: [0, 1], 2: [1, 0], 3: [0, -1], 0: [-1, 0]}\n\t\t(i, j) = (0, 0)\n\t\t(ai, aj) = (i, j)\n\t\twhile i < R and j < C:\n\t\t\tif m[i][j] == 1:\n\t\t\t\tm[i][j] = 0\n\t\t\t\tc += 1\n\t\t\tmv = c % 4\n\t\t\ta = d[mv]\n\t\t\t(ik, jk) = (a[0], a[1])\n\t\t\tif ik + i < 0 or ik + i > R - 1 or jk + j < 0 or (jk + j > C - 1):\n\t\t\t\treturn (i, j)\n\t\t\ti += ik\n\t\t\tj += jk\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\ti = 0\n\t\tj = 0\n\t\td = 'r'\n\t\twhile i < len(matrix) and j < len(matrix[i]):\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif d == 'r':\n\t\t\t\t\tif j + 1 == len(matrix[i]):\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\telse:\n\t\t\t\t\t\tj = j + 1\n\t\t\t\telif d == 'd':\n\t\t\t\t\tif i + 1 == len(matrix):\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\telse:\n\t\t\t\t\t\ti = i + 1\n\t\t\t\telif d == 'l':\n\t\t\t\t\tif j - 1 < 0:\n\t\t\t\t\t\treturn [i, j]\n\t\t\t\t\telse:\n\t\t\t\t\t\tj = j - 1\n\t\t\t\telif i - 1 < 0:\n\t\t\t\t\treturn [i, j]\n\t\t\t\telse:\n\t\t\t\t\ti = i - 1\n\t\t\telif d == 'r':\n\t\t\t\td = 'd'\n\t\t\t\tmatrix[i][j] = 0\n\t\t\telif d == 'd':\n\t\t\t\td = 'l'\n\t\t\t\tmatrix[i][j] = 0\n\t\t\telif d == 'l':\n\t\t\t\td = 'u'\n\t\t\t\tmatrix[i][j] = 0\n\t\t\telse:\n\t\t\t\td = 'r'\n\t\t\t\tmatrix[i][j] = 0\n", "class Solution:\n\n\tdef endPoints(self, matrix, r, c):\n\t\tdx = [-1, 0, 1, 0]\n\t\tdy = [0, 1, 0, -1]\n\t\t(i, j) = (0, 0)\n\t\tcur_dir = 1\n\t\twhile i > -1 and i < r and (j > -1) and (j < c):\n\t\t\tcur_i = i\n\t\t\tcur_j = j\n\t\t\tif matrix[cur_i][cur_j] == 0:\n\t\t\t\ti = i + dx[cur_dir]\n\t\t\t\tj = j + dy[cur_dir]\n\t\t\telse:\n\t\t\t\tcur_dir = (cur_dir + 1) % 4\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\ti += dx[cur_dir]\n\t\t\t\tj = j + dy[cur_dir]\n\t\treturn (cur_i, cur_j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\t(r, c) = (R, C)\n\t\tarr = matrix\n\t\tdirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n\t\tcurr_dir = 0\n\t\ti = j = 0\n\t\twhile 0 <= i < r and 0 <= j < c:\n\t\t\tif arr[i][j] == 0:\n\t\t\t\t(dx, dy) = dirs[curr_dir]\n\t\t\t\ti += dx\n\t\t\t\tj += dy\n\t\t\telse:\n\t\t\t\tarr[i][j] = 0\n\t\t\t\tcurr_dir = (curr_dir + 1) % 4\n\t\t\t\t(dx, dy) = dirs[curr_dir]\n\t\t\tif not (0 <= i < r and 0 <= j < c):\n\t\t\t\treturn (i - dx, j - dy)\n\t\treturn (-1, -1)\n", "class Solution:\n\n\tdef endPoints(self, matrix):\n\t\t(n, m) = (len(matrix), len(matrix[0]))\n\t\tdirection = 0\n\t\t(i, j) = (0, 0)\n\t\tfor _ in range(m * n):\n\t\t\tif i < 0 or i >= n or j < 0 or (j >= m):\n\t\t\t\tif i < 0:\n\t\t\t\t\treturn (i + 1, j)\n\t\t\t\telif i >= n:\n\t\t\t\t\treturn (i - 1, j)\n\t\t\t\telif j < 0:\n\t\t\t\t\treturn (i, j + 1)\n\t\t\t\telse:\n\t\t\t\t\treturn (i, j - 1)\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tdirection = (direction + 1) % 4\n\t\t\t\tmatrix[i][j] = 0\n\t\t\tif direction == 0:\n\t\t\t\tj += 1\n\t\t\telif direction == 1:\n\t\t\t\ti += 1\n\t\t\telif direction == 2:\n\t\t\t\tj -= 1\n\t\t\telse:\n\t\t\t\ti -= 1\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\t(i, j) = (0, 0)\n\t\t(nx, ny) = (0, 1)\n\t\twhile i < R and j < C:\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif nx == -1 and ny == 0:\n\t\t\t\t\t(nx, ny) = (0, 1)\n\t\t\t\telif nx == 0 and ny == 1:\n\t\t\t\t\t(nx, ny) = (1, 0)\n\t\t\t\telif nx == 1 and ny == 0:\n\t\t\t\t\t(nx, ny) = (0, -1)\n\t\t\t\telse:\n\t\t\t\t\t(nx, ny) = (-1, 0)\n\t\t\tif i + nx < 0 or i + nx >= R or j + ny < 0 or (j + ny >= C):\n\t\t\t\treturn [i, j]\n\t\t\ti += nx\n\t\t\tj += ny\n\t\treturn [i, j]\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\ti = 0\n\t\tj = 0\n\t\tdirc = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n\t\tt = 0\n\t\tans = [0, 0]\n\t\twhile i != -1 and i != R and (j != -1) and (j != C):\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif t == 3:\n\t\t\t\t\tt = 0\n\t\t\t\telse:\n\t\t\t\t\tt += 1\n\t\t\tans[0] = i\n\t\t\tans[1] = j\n\t\t\ti += dirc[t][0]\n\t\t\tj += dirc[t][1]\n\t\treturn ans\n", "class Solution:\n\n\tdef fun(self, direc):\n\t\tdic = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}\n\t\treturn dic[direc]\n\n\tdef endPoints(self, matrix, R, C):\n\t\t(i, j) = (0, 0)\n\t\tdic = {'up': (-1, 0), 'right': (0, 1), 'down': (1, 0), 'left': (0, -1)}\n\t\tdirec = 'right'\n\t\twhile True:\n\t\t\tx = matrix[i][j]\n\t\t\tif x == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tdirec = self.fun(direc)\n\t\t\t(a, b) = (dic[direc][0], dic[direc][1])\n\t\t\tif 0 <= i + a < R and 0 <= j + b < C:\n\t\t\t\ti = i + a\n\t\t\t\tj = j + b\n\t\t\telse:\n\t\t\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\n\t\tdef my_move(x, y, dirn):\n\t\t\tmoves = {'right': 'down', 'up': 'right', 'down': 'left', 'left': 'up'}\n\t\t\tif matrix[x][y] == 1:\n\t\t\t\tmatrix[x][y] = 0\n\t\t\t\tdirn = moves[dirn]\n\t\t\tif dirn == 'right':\n\t\t\t\ty += 1\n\t\t\telif dirn == 'left':\n\t\t\t\ty -= 1\n\t\t\telif dirn == 'down':\n\t\t\t\tx += 1\n\t\t\telse:\n\t\t\t\tx -= 1\n\t\t\treturn (x, y, dirn)\n\t\tdirn = 'right'\n\t\t(x, y) = (0, 0)\n\t\twhile True:\n\t\t\ttry:\n\t\t\t\tif matrix[x][y] == 0 or matrix[x][y] == 1:\n\t\t\t\t\tif x < 0 or y < 0:\n\t\t\t\t\t\traise error\n\t\t\t\t\t(result_x, result_y) = (x, y)\n\t\t\t\t\t(x, y, dirn) = my_move(x, y, dirn)\n\t\t\texcept:\n\t\t\t\treturn (result_x, result_y)\n", "class Solution:\n\n\tdef endPoints(self, matrix, R, C):\n\t\tdirection = 0\n\t\tx = 0\n\t\ty = 0\n\t\tprev_x = 0\n\t\tprev_y = 0\n\t\twhile x >= 0 and x < R and (y >= 0) and (y < C):\n\t\t\tprev_x = x\n\t\t\tprev_y = y\n\t\t\tif matrix[x][y] == 1:\n\t\t\t\tmatrix[x][y] = 0\n\t\t\t\tdirection = (direction + 1) % 4\n\t\t\tif direction == 0:\n\t\t\t\ty += 1\n\t\t\telif direction == 1:\n\t\t\t\tx += 1\n\t\t\telif direction == 2:\n\t\t\t\ty -= 1\n\t\t\telse:\n\t\t\t\tx -= 1\n\t\treturn (prev_x, prev_y)\n"]

starter_code:
#User function Template for python3

class Solution:

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

        #code here

difficulty: EASY

source: geekforgeeks

skill_types: ['Data structures']

raw_problem:
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

question:
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:
![image](1.png)
![image](2.png)
![image](3.png)

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<=10000<= matrix[i][j] <=1

image_tags: Others Others Others

data_split: test