The Postmaster wants to write a program to answer the queries regarding letter collection in a city. A city is represented as a matrix mat of size n*m. Each cell represents a house and contains letters which are denoted by a number in the cell. The program should answer q queries which are of following types:
1 i j : To sum all the letters which are at a 1-hop distance from the cell (i,j) in any direction
2 i j : To sum all the letters which are at a 2-hop distance from the cell (i,j) in any direction 
The queries are given in a 2D matrix queries[][].
 
Example 1:
Input: 
n = 4, m = 4
mat = {{1, 2, 3, 4}, 
       {5, 6, 7, 8}, 
       {9, 1, 3, 4}, 
       {1, 2, 3, 4}}
q = 2
queries = {{1 0 1}, 
           {2 0 1}}
Output: 22 29
Explaination: 
For the first query sum is 1+5+6+7+3 = 22. 
For the second query sum is 9+1+3+4+8+4 = 29.
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function matrixSum() which takes n, m, mat, q and queries as input parameters and returns a list of integers where the ith value is the answers for ith query.
 
Expected Time Complexity: O(q)
Expected Auxiliary Space: O(q)
 
Constraints:
1 ≤ n, m ≤ 20
1 ≤ q ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3



class Solution:

    def matrixSum(self, n, m, mat, q, queries):

        # code here

Solutions:
class Solution:

	def matrixSum(self, n, m, mat, q, queries):
		ans = []
		for (t, x, y) in queries:
			temp = 0
			if t == 1:
				for i in range(-1, 2):
					for j in range(-1, 2):
						if i == 0 and j == 0:
							continue
						nx = x + i
						ny = y + j
						if nx < 0 or nx >= n or ny < 0 or (ny >= m):
							continue
						temp += mat[nx][ny]
				ans.append(temp)
			else:
				for i in range(-2, 3):
					for j in range(-2, 3):
						if max(abs(i), abs(j)) != 2:
							continue
						nx = x + i
						ny = y + j
						if nx < 0 or nx >= n or ny < 0 or (ny >= m):
							continue
						temp += mat[nx][ny]
				ans.append(temp)
		return ans


class Solution:

	def matrixSum(self, n, m, mat, q, queries):
		output = []
		for (hop, i, j) in queries:
			output.append(0)
			if j - hop >= 0:
				for k in range(max(0, i - hop), min(n, i + hop)):
					output[-1] += mat[k][j - hop]
			if j + hop < m:
				for k in range(max(0, i - hop + 1), min(n, i + hop + 1)):
					output[-1] += mat[k][j + hop]
			if i - hop >= 0:
				for k in range(max(0, j - hop + 1), min(m, j + hop + 1)):
					output[-1] += mat[i - hop][k]
			if i + hop < n:
				for k in range(max(0, j - hop), min(m, j + hop)):
					output[-1] += mat[i + hop][k]
		return output


class Solution:

	def matrixSum(self, n, m, mat, q, queries):
		ans = []
		for ele in queries:
			(d, i, j) = ele
			temp = 0
			if d == 1:
				if i - 1 >= 0:
					temp += mat[i - 1][j]
				if j - 1 >= 0:
					temp += mat[i][j - 1]
				if i + 1 < n:
					temp += mat[i + 1][j]
				if j + 1 < m:
					temp += mat[i][j + 1]
				if i - 1 >= 0 and j - 1 >= 0:
					temp += mat[i - 1][j - 1]
				if i - 1 >= 0 and j + 1 < m:
					temp += mat[i - 1][j + 1]
				if i + 1 < n and j - 1 >= 0:
					temp += mat[i + 1][j - 1]
				if i + 1 < n and j + 1 < m:
					temp += mat[i + 1][j + 1]
			elif d == 2:
				temp = 0
				if i - 2 >= 0:
					(x, y) = (max(j - 2, 0), min(m, j + 3))
					for k in range(x, y):
						temp += mat[i - 2][k]
				if i + 2 < n:
					(x, y) = (max(j - 2, 0), min(m, j + 3))
					for k in range(x, y):
						temp += mat[i + 2][k]
				if j - 2 >= 0:
					(x, y) = (max(i - 2, 0), min(n, i + 3))
					for k in range(x, y):
						temp += mat[k][j - 2]
				if j + 2 < m:
					(x, y) = (max(i - 2, 0), min(n, i + 3))
					for k in range(x, y):
						temp += mat[k][j + 2]
				if i - 2 >= 0 and j - 2 >= 0:
					temp -= mat[i - 2][j - 2]
				if i - 2 >= 0 and j + 2 < m:
					temp -= mat[i - 2][j + 2]
				if i + 2 < n and j - 2 >= 0:
					temp -= mat[i + 2][j - 2]
				if i + 2 < n and j + 2 < m:
					temp -= mat[i + 2][j + 2]
			ans.append(temp)
		return ans


class Solution:

	def matrixSum(self, n, m, mat, q, que):
		ans = []
		for i in range(q):
			x = que[i][1]
			y = que[i][2]
			s = 0
			if que[i][0] == 1:
				for j in range(x - 1, x + 2):
					for k in range(y - 1, y + 2):
						if k >= 0 and j >= 0 and (j < n) and (k < m):
							s += mat[j][k]
				s -= mat[x][y]
				ans.append(s)
			if que[i][0] == 2:
				for j in range(x - 2, x + 3):
					for k in range(y - 2, y + 3):
						if k >= 0 and j >= 0 and (j < n) and (k < m) and (j == x - 2 or k == y - 2 or j == x + 2 or (k == y + 2)):
							s += mat[j][k]
				ans.append(s)
		return ans


class Solution:

	def matrixSum(self, n, m, mat, q, queries):
		s = []
		for i in range(q):
			p = queries[i][0]
			r = queries[i][1]
			c = queries[i][2]
			ans = 0
			if p == 1:
				row = r - 1
				col = c - 1
				if row >= 0:
					ans = ans + mat[row][c]
				if col >= 0:
					ans = ans + mat[r][col]
				if row >= 0 and col >= 0:
					ans = ans + mat[row][col]
				row = r + 1
				col = c + 1
				if row < n:
					ans = ans + mat[row][c]
				if col < m:
					ans = ans + mat[r][col]
				if row < n and col < m:
					ans = ans + mat[row][col]
				row = r + 1
				col = c - 1
				if row < n and col >= 0:
					ans = ans + mat[row][col]
				row = r - 1
				col = c + 1
				if row >= 0 and col < m:
					ans = ans + mat[row][col]
				s.append(ans)
			else:
				row = r - 2
				col = c - 2
				if row >= 0:
					ans = ans + mat[row][c]
					if c - 1 >= 0:
						ans = ans + mat[row][c - 1]
					if c + 1 < m:
						ans = ans + mat[row][c + 1]
				if col >= 0:
					ans = ans + mat[r][col]
					if r - 1 >= 0:
						ans = ans + mat[r - 1][col]
					if r + 1 < n:
						ans = ans + mat[r + 1][col]
				if row >= 0 and col >= 0:
					ans = ans + mat[row][col]
				row = r + 2
				col = c + 2
				if row < n:
					ans = ans + mat[row][c]
					if c - 1 >= 0:
						ans = ans + mat[row][c - 1]
					if c + 1 < m:
						ans = ans + mat[row][c + 1]
				if col < m:
					ans = ans + mat[r][col]
					if r - 1 >= 0:
						ans = ans + mat[r - 1][col]
					if r + 1 < n:
						ans = ans + mat[r + 1][col]
				if row < n and col < m:
					ans = ans + mat[row][col]
				row = r + 2
				col = c - 2
				if row < n and col >= 0:
					ans = ans + mat[row][col]
				row = r - 2
				col = c + 2
				if row >= 0 and col < m:
					ans = ans + mat[row][col]
				s.append(ans)
		return s


class Solution:

	def matrixSum(self, n, m, mat, q, queries):
		res = []
		for i in range(q):
			sum1 = 0
			dist = queries[i][0]
			ind_i = queries[i][1]
			ind_j = queries[i][2]
			i_mod_top = ind_i - dist
			i_mod_bot = ind_i + dist
			j_mod_left = ind_j - dist
			j_mod_right = ind_j + dist
			for k in range(j_mod_left, j_mod_right + 1):
				if i_mod_top < 0 or i_mod_top >= n or k < 0 or (k >= m):
					continue
				sum1 += mat[i_mod_top][k]
			i_mod_top += 1
			for k in range(j_mod_left, j_mod_right + 1):
				if i_mod_bot < 0 or i_mod_bot >= n or k < 0 or (k >= m):
					continue
				sum1 += mat[i_mod_bot][k]
			i_mod_bot -= 1
			for k in range(i_mod_top, i_mod_bot + 1):
				if j_mod_left < 0 or j_mod_left >= m or k < 0 or (k >= n):
					continue
				sum1 += mat[k][j_mod_left]
			j_mod_left += 1
			for k in range(i_mod_top, i_mod_bot + 1):
				if j_mod_right < 0 or j_mod_right >= m or k < 0 or (k >= n):
					continue
				sum1 += mat[k][j_mod_right]
			j_mod_right -= 1
			res.append(sum1)
		return res


class Solution:

	def matrixSum(self, n, m, mat, q, queries):
		t1 = [-1, 0, 1]
		t2 = [-2, -1, 0, 1, 2]
		res = []
		for g in range(q):
			(z, x, y) = queries[g]
			ans1 = 0
			ans2 = 0
			if z == 1:
				for i in range(len(t1)):
					for j in range(len(t1)):
						if not (t1[i] == 0 and t1[j] == 0):
							if n > x + t1[i] and x + t1[i] >= 0 and (m > y + t1[j]) and (y + t1[j] >= 0):
								ans1 += mat[x + t1[i]][y + t1[j]]
				res.append(ans1)
			elif z == 2:
				for i in range(len(t2)):
					for j in range(len(t2)):
						if abs(t2[i]) == 2 or abs(t2[j]) == 2:
							if n > x + t2[i] and x + t2[i] >= 0 and (m > y + t2[j]) and (y + t2[j] >= 0):
								ans2 += mat[x + t2[i]][y + t2[j]]
				res.append(ans2)
		return res


class Solution:

	def matrixSum(self, n, m, mat, q, queries):
		ans = []
		for i in range(q):
			s = 0
			t = queries[i][0]
			a = queries[i][1]
			b = queries[i][2]
			hop1x = [a - 1, a - 1, a - 1, a, a, a + 1, a + 1, a + 1]
			hop1y = [b - 1, b, b + 1, b - 1, b + 1, b - 1, b, b + 1]
			hop2x = [a - 2, a - 2, a - 2, a - 2, a - 2, a - 1, a - 1, a, a, a + 1, a + 1, a + 2, a + 2, a + 2, a + 2, a + 2]
			hop2y = [b - 2, b - 1, b, b + 1, b + 2, b - 2, b + 2, b - 2, b + 2, b - 2, b + 2, b - 2, b - 1, b, b + 1, b + 2]
			if t == 1:
				for j in range(8):
					if hop1x[j] in list(range(0, n)) and hop1y[j] in list(range(0, m)):
						s += mat[hop1x[j]][hop1y[j]]
			elif t == 2:
				for j in range(16):
					if hop2x[j] in range(0, n) and hop2y[j] in range(0, m):
						s += mat[hop2x[j]][hop2y[j]]
			ans.append(s)
		return ans