Aakriti, Avantika and Mehak are playing 2D Hopscotch. The arena is in the form of a n*m 2D matrix. But the position of the cells is slightly modified as shown below. 
Mehak starts the game from tile (i,j) while Avantika and Aakriti direct her. In each turn Mehak will collect all the stones present (1 or 2) steps away from where she is standing. Avantika can direct Mehak to take 1 step and and Aakriti can direct Mehak to take 2 steps. 
If the director ty is known to you as ty = 0 being Avantika and 1 being Aakriti, find the number of stones that Mehak will collect. 
Example 1:
Input: 
n = 3, m = 3
mat = {{5, 9, 7}, 
       {6, 4, 5}, 
       {8, 1, 2}}
ty = 0, 
i = 1, j = 1
Output: 31
Explaination: 
ty=0, so Avantika is the director. 
ie- Mehak will move only one step in 
any direction to collect the stones.
(0,1), (1,0), (1,2), (2,1), (2,2), (2,0) 
are at a distance of 1 from (1,1). 
Adding them 9+6+5+8+1+2=31.
Example 2:
Input: 
n = 3, m = 3
mat = {{5, 9, 7}, 
       {6, 4, 5}, 
       {8, 1, 2}}
ty = 1, 
i = 1, j = 1
Output: 12
Explaination: 
ty=1, so Aakriti is the director. 
ie- Mehak can move 2 steps. 
(0,0) and (0,2) are the only tiles that 
are at a distance of two from (1,1). 
Adding them gives 5+7=12.
Your Task:
You do not need to read input or print anything. Your task is to complete the function hopscotch() which takes n, m, mat, ty, i and j as input parameters and returns the number of collected stones.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n, m ≤ 1000000
0 ≤ i < n
0 ≤ j < m

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3



class Solution:

    def hopscotch(self, n, m, mat, ty, i, j):

        # code here

Solutions:
class Solution:

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

	def hopscotch(self, n, m, mat, ty, i, j):
		if ty == 0:
			sums = 0
			if j % 2 == 0:
				arr = [[-1, 0], [-1, 1], [0, 1], [1, 0], [0, -1], [-1, -1]]
				for x in arr:
					i1 = i + x[0]
					j1 = j + x[1]
					if self.valid(i1, j1, n, m):
						sums += mat[i1][j1]
			else:
				arr = [[-1, 0], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]]
				for x in arr:
					i1 = i + x[0]
					j1 = j + x[1]
					if self.valid(i1, j1, n, m):
						sums += mat[i1][j1]
		else:
			sums = 0
			if j % 2 == 0:
				arr = [[-2, -1], [-2, 0], [-2, 1], [-1, 2], [0, 2], [1, 2], [1, 1], [2, 0], [1, -1], [1, -2], [0, -2], [-1, -2]]
				for x in arr:
					i1 = i + x[0]
					j1 = j + x[1]
					if self.valid(i1, j1, n, m):
						sums += mat[i1][j1]
			else:
				arr = [[-1, -2], [-1, -1], [-2, 0], [-1, 1], [-1, 2], [0, 2], [1, 2], [2, 1], [2, 0], [2, -1], [1, -2], [0, -2]]
				for x in arr:
					i1 = i + x[0]
					j1 = j + x[1]
					if self.valid(i1, j1, n, m):
						sums += mat[i1][j1]
		return sums


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		output = 0
		if ty == 0:
			if i > 0:
				output += mat[i - 1][j]
			if i < n - 1:
				output += mat[i + 1][j]
			if j > 0:
				output += mat[i][j - 1]
			if j < m - 1:
				output += mat[i][j + 1]
			if j % 2:
				if i < n - 1 and j > 0:
					output += mat[i + 1][j - 1]
				if i < n - 1 and j < m - 1:
					output += mat[i + 1][j + 1]
			else:
				if i > 0 and j > 0:
					output += mat[i - 1][j - 1]
				if i > 0 and j < m - 1:
					output += mat[i - 1][j + 1]
			return output
		if i > 1:
			output += mat[i - 2][j]
		if i < n - 2:
			output += mat[i + 2][j]
		if j > 1:
			output += mat[i][j - 2]
		if j < m - 2:
			output += mat[i][j + 2]
		if i < n - 1 and j < m - 2:
			output += mat[i + 1][j + 2]
		if i > 0 and j > 1:
			output += mat[i - 1][j - 2]
		if i < n - 1 and j > 1:
			output += mat[i + 1][j - 2]
		if i > 0 and j < m - 2:
			output += mat[i - 1][j + 2]
		if j % 2 == 0:
			if i > 1 and j > 0:
				output += mat[i - 2][j - 1]
			if i > 1 and j < m - 1:
				output += mat[i - 2][j + 1]
			if i < n - 1 and j > 0:
				output += mat[i + 1][j - 1]
			if i < n - 1 and j < m - 1:
				output += mat[i + 1][j + 1]
		else:
			if i < n - 2 and j > 0:
				output += mat[i + 2][j - 1]
			if i < n - 2 and j < m - 1:
				output += mat[i + 2][j + 1]
			if i > 0 and j > 0:
				output += mat[i - 1][j - 1]
			if i > 0 and j < m - 1:
				output += mat[i - 1][j + 1]
		return output


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		(i, j) = (2 * i + j % 2, 2 * j)
		res = 0
		if ty == 0:
			for (di, dj) in [[-2, 0], [2, 0], [-1, -2], [-1, 2], [1, -2], [1, 2]]:
				(ni, nj) = ((i + di) // 2, (j + dj) // 2)
				if 0 <= ni < n and 0 <= nj < m:
					res += mat[ni][nj]
		else:
			for (di, dj) in [[-4, 0], [4, 0], [0, -4], [0, 4], [-3, -2], [-3, 2], [3, -2], [3, 2], [-2, -4], [-2, 4], [2, -4], [2, 4]]:
				(ni, nj) = ((i + di) // 2, (j + dj) // 2)
				if 0 <= ni < n and 0 <= nj < m:
					res += mat[ni][nj]
		return res


class Solution:

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

	def hopscotch(self, n, m, mat, ty, i, j):
		sum = 0
		if ty == 0:
			if j % 2 == 0:
				if self.valid(i - 1, j - 1, n, m):
					sum += mat[i - 1][j - 1]
				if self.valid(i - 1, j, n, m):
					sum += mat[i - 1][j]
				if self.valid(i - 1, j + 1, n, m):
					sum += mat[i - 1][j + 1]
				if self.valid(i, j - 1, n, m):
					sum += mat[i][j - 1]
				if self.valid(i, j + 1, n, m):
					sum += mat[i][j + 1]
				if self.valid(i + 1, j, n, m):
					sum += mat[i + 1][j]
			else:
				if self.valid(i - 1, j, n, m):
					sum += mat[i - 1][j]
				if self.valid(i, j - 1, n, m):
					sum += mat[i][j - 1]
				if self.valid(i, j + 1, n, m):
					sum += mat[i][j + 1]
				if self.valid(i + 1, j - 1, n, m):
					sum += mat[i + 1][j - 1]
				if self.valid(i + 1, j, n, m):
					sum += mat[i + 1][j]
				if self.valid(i + 1, j + 1, n, m):
					sum += mat[i + 1][j + 1]
		elif j % 2 == 0:
			if self.valid(i - 2, j - 1, n, m):
				sum += mat[i - 2][j - 1]
			if self.valid(i - 2, j, n, m):
				sum += mat[i - 2][j]
			if self.valid(i - 2, j + 1, n, m):
				sum += mat[i - 2][j + 1]
			if self.valid(i - 1, j - 2, n, m):
				sum += mat[i - 1][j - 2]
			if self.valid(i - 1, j + 2, n, m):
				sum += mat[i - 1][j + 2]
			if self.valid(i, j - 2, n, m):
				sum += mat[i][j - 2]
			if self.valid(i, j + 2, n, m):
				sum += mat[i][j + 2]
			if self.valid(i + 1, j - 2, n, m):
				sum += mat[i + 1][j - 2]
			if self.valid(i + 1, j - 1, n, m):
				sum += mat[i + 1][j - 1]
			if self.valid(i + 1, j + 1, n, m):
				sum += mat[i + 1][j + 1]
			if self.valid(i + 1, j + 2, n, m):
				sum += mat[i + 1][j + 2]
			if self.valid(i + 2, j, n, m):
				sum += mat[i + 2][j]
		else:
			if self.valid(i - 1, j - 2, n, m):
				sum += mat[i - 1][j - 2]
			if self.valid(i - 1, j - 1, n, m):
				sum += mat[i - 1][j - 1]
			if self.valid(i - 2, j, n, m):
				sum += mat[i - 2][j]
			if self.valid(i - 1, j + 1, n, m):
				sum += mat[i - 1][j + 1]
			if self.valid(i - 1, j + 2, n, m):
				sum += mat[i - 1][j + 2]
			if self.valid(i, j - 2, n, m):
				sum += mat[i][j - 2]
			if self.valid(i, j + 2, n, m):
				sum += mat[i][j + 2]
			if self.valid(i + 1, j - 2, n, m):
				sum += mat[i + 1][j - 2]
			if self.valid(i + 1, j + 2, n, m):
				sum += mat[i + 1][j + 2]
			if self.valid(i + 2, j - 1, n, m):
				sum += mat[i + 2][j - 1]
			if self.valid(i + 2, j, n, m):
				sum += mat[i + 2][j]
			if self.valid(i + 2, j + 1, n, m):
				sum += mat[i + 2][j + 1]
		return sum


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		res = []
		cells = [(-1 + i, -2 + j), (-2 + i, -1 + j), (-2 + i, 0 + j), (-2 + i, +1 + j), (-1 + i, +2 + j), (0 + i, +2 + j), (+1 + i, +2 + j), (+1 + i, +1 + j), (+2 + i, 0 + j), (+1 + i, -1 + j), (+1 + i, -2 + j), (0 + i, -2 + j)]
		cells1 = [(-1 + i, -2 + j), (-1 + i, -1 + j), (-2 + i, 0 + j), (-1 + i, +1 + j), (-1 + i, +2 + j), (0 + i, +2 + j), (+1 + i, +2 + j), (+2 + i, +1 + j), (+2 + i, 0 + j), (+2 + i, -1 + j), (+1 + i, -2 + j), (0 + i, -2 + j)]
		if ty == 0:
			if j % 2 == 0:
				for a in range(j - 1, j + 2):
					x = i - 1
					if m > a >= 0 and n > x >= 0:
						res.append(mat[x][a])
					x1 = i
					if m > a >= 0 and n > x1 >= 0 and (a != j):
						res.append(mat[x1][a])
					x2 = i + 1
					if a == j and n > x2 >= 0:
						res.append(mat[x2][a])
			else:
				for a in range(j - 1, j + 2):
					x = i + 1
					if m > a >= 0 and n > x >= 0:
						res.append(mat[x][a])
					x1 = i
					if m > a >= 0 and n > x1 >= 0 and (a != j):
						res.append(mat[x1][a])
					x2 = i - 1
					if a == j and n > x2 >= 0:
						res.append(mat[x2][a])
		elif j % 2 == 0:
			for (rol, col) in cells:
				if n > rol >= 0 and m > col >= 0:
					res.append(mat[rol][col])
		else:
			for (rol, col) in cells1:
				if n > rol >= 0 and m > col >= 0:
					res.append(mat[rol][col])
		return sum(res)


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		dir = [[(-1, 0), (1, 0), (-1, -1), (-1, 1), (0, -1), (0, 1)], [(-1, 0), (1, 0), (0, -1), (0, 1), (1, -1), (1, 1)]]
		ans = 0
		for (dx, dy) in dir[j % 2]:
			x = i + dx
			y = j + dy
			if x >= 0 and x < n and (y >= 0) and (y < m):
				if ty:
					for (dx2, dy2) in dir[y % 2]:
						x2 = x + dx2
						y2 = y + dy2
						if x2 >= 0 and x2 < n and (y2 >= 0) and (y2 < m):
							d0 = (x2 - i, y2 - j)
							if d0 != (0, 0) and d0 not in dir[j % 2] and mat[x2][y2]:
								ans += mat[x2][y2]
								mat[x2][y2] = 0
				else:
					ans += mat[x][y]
		return ans


class Solution:

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

	def hopscotch(self, n, m, mat, ty, i, j):
		stone = 0
		if ty == 0:
			if j % 2 == 0:
				if self.isArea(n, m, i - 1, j):
					stone += mat[i - 1][j]
				if self.isArea(n, m, i - 1, j + 1):
					stone += mat[i - 1][j + 1]
				if self.isArea(n, m, i, j + 1):
					stone += mat[i][j + 1]
				if self.isArea(n, m, i + 1, j):
					stone += mat[i + 1][j]
				if self.isArea(n, m, i, j - 1):
					stone += mat[i][j - 1]
				if self.isArea(n, m, i - 1, j - 1):
					stone += mat[i - 1][j - 1]
			else:
				if self.isArea(n, m, i - 1, j):
					stone += mat[i - 1][j]
				if self.isArea(n, m, i, j + 1):
					stone += mat[i][j + 1]
				if self.isArea(n, m, i + 1, j + 1):
					stone += mat[i + 1][j + 1]
				if self.isArea(n, m, i + 1, j):
					stone += mat[i + 1][j]
				if self.isArea(n, m, i + 1, j - 1):
					stone += mat[i + 1][j - 1]
				if self.isArea(n, m, i, j - 1):
					stone += mat[i][j - 1]
		elif j % 2 == 0:
			if self.isArea(n, m, i - 2, j):
				stone += mat[i - 2][j]
			if self.isArea(n, m, i - 2, j + 1):
				stone += mat[i - 2][j + 1]
			if self.isArea(n, m, i - 1, j + 2):
				stone += mat[i - 1][j + 2]
			if self.isArea(n, m, i, j + 2):
				stone += mat[i][j + 2]
			if self.isArea(n, m, i + 1, j + 2):
				stone += mat[i + 1][j + 2]
			if self.isArea(n, m, i + 1, j + 1):
				stone += mat[i + 1][j + 1]
			if self.isArea(n, m, i + 2, j):
				stone += mat[i + 2][j]
			if self.isArea(n, m, i + 1, j - 1):
				stone += mat[i + 1][j - 1]
			if self.isArea(n, m, i + 1, j - 2):
				stone += mat[i + 1][j - 2]
			if self.isArea(n, m, i, j - 2):
				stone += mat[i][j - 2]
			if self.isArea(n, m, i - 2, j - 1):
				stone += mat[i - 2][j - 1]
			if self.isArea(n, m, i - 1, j - 2):
				stone += mat[i - 1][j - 2]
		else:
			if self.isArea(n, m, i - 2, j):
				stone += mat[i - 2][j]
			if self.isArea(n, m, i - 1, j + 1):
				stone += mat[i - 1][j + 1]
			if self.isArea(n, m, i - 1, j + 2):
				stone += mat[i - 1][j + 2]
			if self.isArea(n, m, i, j + 2):
				stone += mat[i][j + 2]
			if self.isArea(n, m, i + 1, j + 2):
				stone += mat[i + 1][j + 2]
			if self.isArea(n, m, i + 2, j + 1):
				stone += mat[i + 2][j + 1]
			if self.isArea(n, m, i + 2, j):
				stone += mat[i + 2][j]
			if self.isArea(n, m, i + 2, j - 1):
				stone += mat[i + 2][j - 1]
			if self.isArea(n, m, i + 1, j - 2):
				stone += mat[i + 1][j - 2]
			if self.isArea(n, m, i, j - 2):
				stone += mat[i][j - 2]
			if self.isArea(n, m, i - 1, j - 2):
				stone += mat[i - 1][j - 2]
			if self.isArea(n, m, i - 1, j - 1):
				stone += mat[i - 1][j - 1]
		return stone


class Solution:

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

	def neighbouring_vertices(self, i, j):
		nv = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
		if j % 2 == 0:
			nv.append((i - 1, j - 1))
			nv.append((i - 1, j + 1))
		else:
			nv.append((i + 1, j - 1))
			nv.append((i + 1, j + 1))
		return [v for v in nv if self.in_board(v[0], v[1])]

	def hopscotch(self, n, m, mat, ty, i, j):
		self.n = n
		self.m = m
		neighbours = self.neighbouring_vertices(i, j)
		if ty == 0:
			collect = neighbours
		else:
			collect = [v for nv in neighbours for v in self.neighbouring_vertices(nv[0], nv[1]) if v not in neighbours and v != (i, j)]
			collect = list(set(collect))
		res = 0
		for (si, sj) in collect:
			res += mat[si][sj]
		return res


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		result = 0
		if ty == 0:
			temp = [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]
			lst = [(p, q) for (p, q) in temp if n > p >= 0 and m > q >= 0]
			if j % 2 == 0 and i - 1 >= 0:
				if j - 1 >= 0:
					lst.append((i - 1, j - 1))
				if j + 1 < m:
					lst.append((i - 1, j + 1))
			elif j % 2 == 1 and i + 1 < n:
				if j - 1 >= 0:
					lst.append((i + 1, j - 1))
				if j + 1 < m:
					lst.append((i + 1, j + 1))
			for (p, q) in lst:
				result += mat[p][q]
		else:
			temp = [(i - 2, j), (i + 2, j), (i, j - 2), (i - 1, j - 2), (i + 1, j - 2)]
			temp += [(i, j + 2), (i - 1, j + 2), (i + 1, j + 2)]
			lst = [(p, q) for (p, q) in temp if n > p >= 0 and m > q >= 0]
			if j % 2 == 1:
				if i - 1 >= 0:
					if j - 1 >= 0:
						lst.append((i - 1, j - 1))
					if j + 1 < m:
						lst.append((i - 1, j + 1))
				if i + 2 < n:
					if j - 1 >= 0:
						lst.append((i + 2, j - 1))
					if j + 1 < m:
						lst.append((i + 2, j + 1))
			else:
				if i - 2 >= 0:
					if j - 1 >= 0:
						lst.append((i - 2, j - 1))
					if j + 1 < m:
						lst.append((i - 2, j + 1))
				if i + 1 < n:
					if j - 1 >= 0:
						lst.append((i + 1, j - 1))
					if j + 1 < m:
						lst.append((i + 1, j + 1))
			for (p, q) in lst:
				result += mat[p][q]
		return result


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		tot = 0
		if ty == 0:
			if j & 1:
				possibilities = ((i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1))
			else:
				possibilities = ((i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j + 1), (i + 1, j))
		elif j & 1:
			possibilities = ((i - 2, j), (i - 1, j - 2), (i - 1, j - 1), (i - 1, j + 1), (i - 1, j + 2), (i, j - 2), (i, j + 2), (i + 1, j - 2), (i + 1, j + 2), (i + 2, j - 1), (i + 2, j), (i + 2, j + 1))
		else:
			possibilities = ((i - 2, j - 1), (i - 2, j), (i - 2, j + 1), (i - 1, j - 2), (i - 1, j + 2), (i, j - 2), (i, j + 2), (i + 1, j - 2), (i + 1, j - 1), (i + 1, j + 1), (i + 1, j + 2), (i + 2, j))
		for (x, y) in possibilities:
			if 0 <= x < n and 0 <= y < m:
				tot += mat[x][y]
		return tot


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		if j % 2 == 0:
			AK = [[-2, 0], [-2, -1], [-1, -2], [0, -2], [1, -2], [1, -1], [2, 0], [1, 1], [1, 2], [0, 2], [-1, 2], [-2, 1]]
			AV = [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 0], [0, -1]]
		else:
			AK = [[-2, 0], [-1, -1], [-1, 1], [-1, -2], [0, -2], [1, -2], [2, -1], [2, 0], [2, 1], [1, 2], [0, 2], [-1, 2]]
			AV = [[0, -1], [-1, 0], [0, 1], [1, 1], [1, 0], [1, -1]]
		use = AV
		if ty == 1:
			use = AK
		res = 0
		for (x, y) in use:
			p = i + x
			q = j + y
			if p >= 0 and p < n and (q >= 0) and (q < m):
				res += mat[p][q]
		return res


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		ans = 0

		def isValid(mat, i, j, n, m):
			if i >= 0 and j >= 0 and (i < n) and (j < m):
				return True
		if ty == 0:
			if isValid(mat, i + 1, j, n, m):
				ans = ans + mat[i + 1][j]
			if isValid(mat, i - 1, j, n, m):
				ans = ans + mat[i - 1][j]
			if j % 2 == 0:
				if isValid(mat, i, j - 1, n, m):
					ans = ans + mat[i][j - 1]
				if isValid(mat, i, j + 1, n, m):
					ans = ans + mat[i][j + 1]
				if isValid(mat, i - 1, j - 1, n, m):
					ans = ans + mat[i - 1][j - 1]
				if isValid(mat, i - 1, j + 1, n, m):
					ans = ans + mat[i - 1][j + 1]
			else:
				if isValid(mat, i + 1, j - 1, n, m):
					ans = ans + mat[i + 1][j - 1]
				if isValid(mat, i + 1, j + 1, n, m):
					ans = ans + mat[i + 1][j + 1]
				if isValid(mat, i, j - 1, n, m):
					ans = ans + mat[i][j - 1]
				if isValid(mat, i, j + 1, n, m):
					ans = ans + mat[i][j + 1]
		else:
			if isValid(mat, i - 2, j, n, m):
				ans = ans + mat[i - 2][j]
			if isValid(mat, i + 2, j, n, m):
				ans = ans + mat[i + 2][j]
			if isValid(mat, i, j - 2, n, m):
				ans = ans + mat[i][j - 2]
			if isValid(mat, i, j + 2, n, m):
				ans = ans + mat[i][j + 2]
			if isValid(mat, i - 1, j - 2, n, m):
				ans = ans + mat[i - 1][j - 2]
			if isValid(mat, i + 1, j - 2, n, m):
				ans = ans + mat[i + 1][j - 2]
			if isValid(mat, i - 1, j + 2, n, m):
				ans = ans + mat[i - 1][j + 2]
			if isValid(mat, i + 1, j + 2, n, m):
				ans = ans + mat[i + 1][j + 2]
			if j % 2 == 0:
				if isValid(mat, i - 2, j - 1, n, m):
					ans = ans + mat[i - 2][j - 1]
				if isValid(mat, i - 2, j + 1, n, m):
					ans = ans + mat[i - 2][j + 1]
				if isValid(mat, i + 1, j - 1, n, m):
					ans = ans + mat[i + 1][j - 1]
				if isValid(mat, i + 1, j + 1, n, m):
					ans = ans + mat[i + 1][j + 1]
			else:
				if isValid(mat, i - 1, j - 1, n, m):
					ans = ans + mat[i - 1][j - 1]
				if isValid(mat, i - 1, j + 1, n, m):
					ans = ans + mat[i - 1][j + 1]
				if isValid(mat, i + 2, j - 1, n, m):
					ans = ans + mat[i + 2][j - 1]
				if isValid(mat, i + 2, j + 1, n, m):
					ans = ans + mat[i + 2][j + 1]
		return ans


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		ans = 0
		if ty == 0:
			(r, l, u, d, ur, ul, lr, ll) = (0, 0, 0, 0, 0, 0, 0, 0)
			if i + 1 < n:
				d = mat[i + 1][j]
				if j + 1 < m:
					lr = mat[i + 1][j + 1]
				if j - 1 >= 0:
					ll = mat[i + 1][j - 1]
			if i - 1 >= 0:
				u = mat[i - 1][j]
				if j + 1 < m:
					ur = mat[i - 1][j + 1]
				if j - 1 >= 0:
					ul = mat[i - 1][j - 1]
			if j + 1 < m:
				r = mat[i][j + 1]
			if j - 1 >= 0:
				l = mat[i][j - 1]
			if j % 2 == 1:
				ans += r + l + u + d + lr + ll
			else:
				ans += r + l + u + d + ul + ur
		elif j % 2 == 1:
			if i - 2 >= 0:
				ans += mat[i - 2][j]
			if i - 1 >= 0:
				if j - 2 >= 0:
					ans += mat[i - 1][j - 2]
				if j - 1 >= 0:
					ans += mat[i - 1][j - 1]
				if j + 1 < m:
					ans += mat[i - 1][j + 1]
				if j + 2 < m:
					ans += mat[i - 1][j + 2]
			if j - 2 >= 0:
				ans += mat[i][j - 2]
			if j + 2 < m:
				ans += mat[i][j + 2]
			if i + 1 < n:
				if j - 2 >= 0:
					ans += mat[i + 1][j - 2]
				if j + 2 < m:
					ans += mat[i + 1][j + 2]
			if i + 2 < n:
				ans += mat[i + 2][j]
				if j - 1 >= 0:
					ans += mat[i + 2][j - 1]
				if j + 1 < m:
					ans += mat[i + 2][j + 1]
		else:
			if i - 2 >= 0:
				ans += mat[i - 2][j]
				if j - 1 >= 0:
					ans += mat[i - 2][j - 1]
				if j + 1 < m:
					ans += mat[i - 2][j + 1]
			if i - 1 >= 0:
				if j - 2 >= 0:
					ans += mat[i - 1][j - 2]
				if j + 2 < m:
					ans += mat[i - 1][j + 2]
			if j - 2 >= 0:
				ans += mat[i][j - 2]
			if j + 2 < m:
				ans += mat[i][j + 2]
			if i + 1 < n:
				if j - 2 >= 0:
					ans += mat[i + 1][j - 2]
				if j + 2 < m:
					ans += mat[i + 1][j + 2]
				if j - 1 >= 0:
					ans += mat[i + 1][j - 1]
				if j + 1 < m:
					ans += mat[i + 1][j + 1]
			if i + 2 < n:
				ans += mat[i + 2][j]
		return ans


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		ans = 0
		t = -(-1) ** (j & 1)
		dx = [[0, -1, 0, 1, t, t], [0, -2, 0, 2, -1, -1, 1, 1, -t, -t, 2 * t, 2 * t]]
		dy = [[-1, 0, 1, 0, -1, 1], [-2, 0, 2, 0, -2, 2, -2, 2, -1, 1, -1, 1]]
		k = 0
		while k < 6 * (ty + 1):
			x = i + dx[ty][k]
			y = j + dy[ty][k]
			if x >= 0 and x < n and (y >= 0) and (y < m):
				ans += mat[x][y]
			k += 1
		return ans


class Solution:

	def hopscotch(self, N, M, grid, ty, i, j):
		if ty == 0:
			if j & 1 == 1:
				dirs = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, -1], [1, 1]]
			else:
				dirs = [[-1, 0], [-1, 1], [0, 1], [1, 0], [0, -1], [-1, -1]]
		else:
			dirs = [[2, 0], [0, 2], [-2, 0], [0, -2]]
			if j & 1 == 0:
				dirs.extend([[-2, 1], [-1, 2], [1, 2], [1, 1], [1, -1], [1, -2], [-1, -2], [-2, -1]])
			else:
				dirs.extend([[-1, -2], [-1, -1], [-1, 1], [-1, 2], [1, 2], [2, 1], [1, -2], [2, -1]])
		res = 0
		for (x, y) in dirs:
			(nx, ny) = (x + i, y + j)
			if 0 <= nx < N and 0 <= ny < M:
				res += grid[nx][ny]
		return res


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		arr1x = [-1, 0, 0, 1, 1, 1]
		arr1y = [0, -1, 1, -1, 0, 1]
		arr2x = [-1, -1, -1, 0, 0, 1]
		arr2y = [-1, 0, 1, -1, 1, 0]
		arr3x = [-2, -2, -1, 0, 1, 1, 2, 1, 1, 0, -1, -2]
		arr3y = [0, 1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -1]
		arr4x = [-2, -1, -1, 0, 1, 2, 2, 2, 1, 0, -1, -1]
		arr4y = [0, 1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -1]
		sum1 = 0
		if ty == 0:
			if j % 2 == 1:
				for index in range(len(arr1x)):
					newx = i + arr1x[index]
					newy = j + arr1y[index]
					if newx >= 0 and newy >= 0 and (newx < n) and (newy < m):
						sum1 += mat[newx][newy]
			else:
				for index in range(len(arr2x)):
					newx = i + arr2x[index]
					newy = j + arr2y[index]
					if newx >= 0 and newy >= 0 and (newx < n) and (newy < m):
						sum1 += mat[newx][newy]
		elif ty == 1:
			if j % 2 == 0:
				for index in range(len(arr3x)):
					newx = i + arr3x[index]
					newy = j + arr3y[index]
					if newx >= 0 and newy >= 0 and (newx < n) and (newy < m):
						sum1 += mat[newx][newy]
			else:
				for index in range(len(arr4x)):
					newx = i + arr4x[index]
					newy = j + arr4y[index]
					if newx >= 0 and newy >= 0 and (newx < n) and (newy < m):
						sum1 += mat[newx][newy]
		return sum1


class Solution:

	def check(self, i, j, n, m):
		if i < 0 or j < 0 or i > n - 1 or (j > m - 1):
			return False
		return True

	def hopscotch(self, n, m, mat, ty, i, j):
		ans = 0
		if ty == 0:
			if j % 2 == 0:
				if self.check(i - 1, j - 1, n, m):
					ans += mat[i - 1][j - 1]
				if self.check(i - 1, j, n, m):
					ans += mat[i - 1][j]
				if self.check(i - 1, j + 1, n, m):
					ans += mat[i - 1][j + 1]
				if self.check(i, j - 1, n, m):
					ans += mat[i][j - 1]
				if self.check(i, j + 1, n, m):
					ans += mat[i][j + 1]
				if self.check(i + 1, j, n, m):
					ans += mat[i + 1][j]
			else:
				if self.check(i - 1, j, n, m):
					ans += mat[i - 1][j]
				if self.check(i, j - 1, n, m):
					ans += mat[i][j - 1]
				if self.check(i, j + 1, n, m):
					ans += mat[i][j + 1]
				if self.check(i + 1, j - 1, n, m):
					ans += mat[i + 1][j - 1]
				if self.check(i + 1, j, n, m):
					ans += mat[i + 1][j]
				if self.check(i + 1, j + 1, n, m):
					ans += mat[i + 1][j + 1]
			return ans
		if j % 2 == 1:
			if self.check(i - 1, j - 2, n, m):
				ans += mat[i - 1][j - 2]
			if self.check(i - 1, j - 1, n, m):
				ans += mat[i - 1][j - 1]
			if self.check(i - 2, j, n, m):
				ans += mat[i - 2][j]
			if self.check(i - 1, j + 1, n, m):
				ans += mat[i - 1][j + 1]
			if self.check(i - 1, j + 2, n, m):
				ans += mat[i - 1][j + 2]
			if self.check(i, j - 2, n, m):
				ans += mat[i][j - 2]
			if self.check(i, j + 2, n, m):
				ans += mat[i][j + 2]
			if self.check(i + 1, j - 2, n, m):
				ans += mat[i + 1][j - 2]
			if self.check(i + 2, j - 1, n, m):
				ans += mat[i + 2][j - 1]
			if self.check(i + 2, j, n, m):
				ans += mat[i + 2][j]
			if self.check(i + 2, j + 1, n, m):
				ans += mat[i + 2][j + 1]
			if self.check(i + 1, j + 2, n, m):
				ans += mat[i + 1][j + 2]
		else:
			if self.check(i - 1, j - 2, n, m):
				ans += mat[i - 1][j - 2]
			if self.check(i - 2, j - 1, n, m):
				ans += mat[i - 2][j - 1]
			if self.check(i - 2, j, n, m):
				ans += mat[i - 2][j]
			if self.check(i - 2, j + 1, n, m):
				ans += mat[i - 2][j + 1]
			if self.check(i - 1, j + 2, n, m):
				ans += mat[i - 1][j + 2]
			if self.check(i, j - 2, n, m):
				ans += mat[i][j - 2]
			if self.check(i, j + 2, n, m):
				ans += mat[i][j + 2]
			if self.check(i + 1, j - 2, n, m):
				ans += mat[i + 1][j - 2]
			if self.check(i + 1, j - 1, n, m):
				ans += mat[i + 1][j - 1]
			if self.check(i + 2, j, n, m):
				ans += mat[i + 2][j]
			if self.check(i + 1, j + 1, n, m):
				ans += mat[i + 1][j + 1]
			if self.check(i + 1, j + 2, n, m):
				ans += mat[i + 1][j + 2]
		return ans


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		if ty == 0:
			sm = 0
			if j % 2 != 0:
				arr = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [1, -1]]
				for k in arr:
					i1 = i + k[0]
					j1 = j + k[1]
					if i1 >= 0 and j1 >= 0 and (i1 < n) and (j1 < m):
						sm += mat[i1][j1]
			else:
				arr = [[-1, -1], [-1, 1], [1, 0], [0, 1], [-1, 0], [0, -1]]
				for k in arr:
					i1 = i + k[0]
					j1 = j + k[1]
					if i1 >= 0 and j1 >= 0 and (i1 < n) and (j1 < m):
						sm += mat[i1][j1]
		else:
			sm = 0
			if j % 2 == 1:
				arr = [[-1, 1], [-1, -1], [2, 0], [-2, 0], [2, -1], [2, 1], [-1, -2], [-1, 2], [0, -2], [0, 2], [1, -2], [1, 2]]
				for k in arr:
					i1 = i + k[0]
					j1 = j + k[1]
					if i1 >= 0 and j1 >= 0 and (i1 < n) and (j1 < m):
						sm += mat[i1][j1]
			else:
				arr = [[-2, 1], [1, -1], [2, 0], [-2, 0], [-2, -1], [1, 1], [-1, -2], [-1, 2], [0, -2], [0, 2], [1, -2], [1, 2]]
				for k in arr:
					i1 = i + k[0]
					j1 = j + k[1]
					if i1 >= 0 and j1 >= 0 and (i1 < n) and (j1 < m):
						sm += mat[i1][j1]
		return sm


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		odd = [[-1, 0], [0, -1], [0, 1], [1, 0], [1, 1], [1, -1]]
		even = [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 0], [0, -1]]
		stones = 0
		if j % 2:
			moves = odd
		else:
			moves = even
		if ty == 0:
			for __m in moves:
				if __m[0] + i >= 0 and __m[0] + i < n and (__m[1] + j >= 0) and (__m[1] + j < m):
					stones += mat[__m[0] + i][__m[1] + j]
		else:
			bmoves = [[-2, 0], [2, 0], [0, -2], [0, 2], [-1, -2], [-1, 2], [1, -2], [1, 2]]
			omoves = [[-1, -1], [-1, 1], [2, -1], [2, 1]]
			emoves = [[1, -1], [1, 1], [-2, -1], [-2, 1]]
			for __m in bmoves:
				if i + __m[0] >= 0 and i + __m[0] < n and (j + __m[1] >= 0) and (j + __m[1] < m):
					stones += mat[__m[0] + i][__m[1] + j]
			if j % 2:
				for __m in omoves:
					if i + __m[0] >= 0 and i + __m[0] < n and (j + __m[1] >= 0) and (j + __m[1] < m):
						stones += mat[__m[0] + i][__m[1] + j]
			else:
				for __m in emoves:
					if i + __m[0] >= 0 and i + __m[0] < n and (j + __m[1] >= 0) and (j + __m[1] < m):
						stones += mat[__m[0] + i][__m[1] + j]
		return stones


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		if j % 2 != 0:
			one_step = [[0, -1], [0, 1], [-1, 0], [1, -1], [1, 0], [1, 1]]
		else:
			one_step = [[-1, -1], [-1, 1], [-1, 0], [0, -1], [0, 1], [1, 0]]
		ans = 0
		if ty == 0:
			for (dx, dy) in one_step:
				x = i + dx
				y = j + dy
				if x < 0 or x >= n or y < 0 or (y >= m):
					continue
				else:
					ans += mat[x][y]
		else:
			visited = [[i, j]]
			for (dx, dy) in one_step:
				x = i + dx
				y = j + dy
				if x < 0 or x >= n or y < 0 or (y >= m):
					continue
				else:
					visited.append([x, y])
			new_visited = visited.copy()
			for (new_i, new_j) in new_visited:
				if new_j % 2 != 0:
					one_step = [[0, -1], [0, 1], [-1, 0], [1, -1], [1, 0], [1, 1]]
				else:
					one_step = [[-1, -1], [-1, 1], [-1, 0], [0, -1], [0, 1], [1, 0]]
				for (new_dx, new_dy) in one_step:
					new_x = new_i + new_dx
					new_y = new_j + new_dy
					if [new_x, new_y] in visited or new_x < 0 or new_x >= n or (new_y < 0) or (new_y >= m):
						continue
					else:
						ans += mat[new_x][new_y]
						visited.append([new_x, new_y])
		return ans


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):

		def func(x, y):
			if x >= 0 and y >= 0 and (x < n) and (y < m):
				return mat[x][y]
			return 0
		res = 0
		if ty == 0:
			res += func(i + 1, j) + func(i, j + 1) + func(i - 1, j) + func(i, j - 1)
			if j & 1:
				res += func(i + 1, j - 1) + func(i + 1, j + 1)
			else:
				res += func(i - 1, j - 1) + func(i - 1, j + 1)
		else:
			res += func(i - 2, j) + func(i, j - 2) + func(i + 2, j) + func(i, j + 2)
			if j & 1:
				res += func(i - 1, j - 1) + func(i - 1, j + 1) + func(i - 1, j - 2) + func(i - 1, j + 2) + func(i + 1, j - 2) + func(i + 1, j + 2) + func(i + 2, j - 1) + func(i + 2, j + 1)
			else:
				res += func(i + 1, j - 1) + func(i + 1, j + 1) + func(i + 1, j - 2) + func(i + 1, j + 2) + func(i - 1, j + 2) + func(i - 1, j - 2) + func(i - 2, j + 1) + func(i - 2, j - 1)
		return res


class Solution:

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

	def hopscotch(self, n, m, mat, ty, i, j):
		res = 0
		if ty == 0:
			if j % 2:
				dir = [[-1, 0], [1, 0], [0, 1], [1, -1], [1, 1], [0, -1]]
				for (nx, ny) in dir:
					if self.valid(i + nx, j + ny, n, m):
						res += mat[i + nx][j + ny]
			else:
				dir = [[-1, 0], [1, 0], [0, 1], [-1, 1], [-1, -1], [0, -1]]
				for (nx, ny) in dir:
					if self.valid(i + nx, j + ny, n, m):
						res += mat[i + nx][j + ny]
		elif j % 2:
			dir = [[-1, -2], [-1, -1], [-2, 0], [-1, 1], [-1, 2], [0, 2], [1, 2], [2, 1], [2, 0], [2, -1], [1, -2], [0, -2]]
			for (nx, ny) in dir:
				if self.valid(i + nx, j + ny, n, m):
					res += mat[i + nx][j + ny]
		else:
			dir = [[-2, -1], [-2, 0], [-2, 1], [-1, 2], [0, 2], [1, 2], [1, 1], [2, 0], [1, -1], [1, -2], [0, -2], [-1, -2]]
			for (nx, ny) in dir:
				if self.valid(i + nx, j + ny, n, m):
					res += mat[i + nx][j + ny]
		return res


from collections import deque

class Solution:

	def hopscotch(self, n, m, mat, ky, i, j):
		xo = [-1, 0, 1, 1, 1, 0]
		yo = [0, -1, 0, -1, 1, 1]
		xe = [-1, -1, -1, 0, 0, 1]
		ye = [-1, 0, 1, -1, 1, 0]

		def isValid(i, j, d):
			if 0 <= i < n and 0 <= j < m and (not vis[i][j]) and (d <= ky + 1):
				return True
			return False
		q = deque([(i, j, 0)])
		res = [0] * 2
		vis = [[0] * m for _ in range(n)]
		vis[i][j] = 1
		while q:
			(r, c, d) = q.popleft()
			if d:
				res[d - 1] += mat[r][c]
			for k in range(6):
				if c & 1:
					tx = r + xo[k]
					ty = c + yo[k]
				else:
					tx = r + xe[k]
					ty = c + ye[k]
				if isValid(tx, ty, d + 1):
					vis[tx][ty] = 1
					q.append((tx, ty, d + 1))
		return res[ky]


from collections import deque

class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		if ty % 2 == 0:
			if j % 2 == 0:
				row = [-1, -1, 0, 1, 0, -1]
				col = [0, 1, 1, 0, -1, -1]
			else:
				row = [-1, 0, 1, 1, 1, 0]
				col = [0, 1, 1, 0, -1, -1]
		elif j % 2 == 0:
			row = [-2, -2, -2, -1, -1, 0, 0, 1, 1, 1, 1, 2]
			col = [-1, 0, 1, 2, -2, 2, -2, 2, 1, -1, -2, 0]
		else:
			row = [-1, -1, -2, -1, -1, 0, 1, 2, 2, 2, 1, 0]
			col = [-2, -1, 0, 1, 2, 2, 2, 1, 0, -1, -2, -2]
		res = 0
		for x in range(len(row)):
			a = i + row[x]
			b = j + col[x]
			if a >= 0 and b >= 0 and (a < n) and (b < m):
				res += mat[a][b]
		return res


class Solution:

	def hopscotch(self, n, m, mat, ty, i, j):
		x = 0
		if ty == 0:
			for a in range(max(i - 1, 0), i + 2):
				for b in range(max(j - 1, 0), j + 2):
					try:
						x = x + mat[a][b]
					except IndexError:
						pass
			x = x - mat[i][j]
			if j % 2 == 0:
				if j >= 1:
					try:
						x = x - mat[i + 1][j - 1]
					except IndexError:
						pass
				try:
					x = x - mat[i + 1][j + 1]
				except IndexError:
					pass
				return x
			else:
				if i >= 1:
					try:
						x = x - mat[i - 1][j + 1]
					except IndexError:
						pass
				if i >= 1 and j >= 1:
					try:
						x = x - mat[i - 1][j - 1]
					except IndexError:
						pass
				return x
		else:
			for a in range(max(i - 1, 0), i + 2):
				try:
					x = x + mat[a][j + 2]
				except IndexError:
					pass
			if j >= 2:
				for a in range(max(i - 1, 0), i + 2):
					try:
						x = x + mat[a][j - 2]
					except IndexError:
						pass
			if j % 2 == 0:
				if i >= 2:
					for a in range(max(j - 1, 0), j + 2):
						try:
							x = x + mat[i - 2][a]
						except IndexError:
							pass
				if j >= 1:
					try:
						x = x + mat[i + 1][j - 1]
					except IndexError:
						pass
				try:
					x = x + mat[i + 1][j + 1]
				except IndexError:
					pass
				try:
					x = x + mat[i + 2][j]
				except IndexError:
					pass
				return x
			else:
				for b in range(max(j - 1, 0), j + 2):
					try:
						x = x + mat[i + 2][b]
					except IndexError:
						pass
				if j >= 1 and i >= 1:
					try:
						x = x + mat[i - 1][j - 1]
					except IndexError:
						pass
				if i >= 1:
					try:
						x = x + mat[max(i - 1, 0)][j + 1]
					except IndexError:
						pass
				if i >= 2:
					try:
						x = x + mat[i - 2][j]
					except IndexError:
						pass
				return x