Given the chessboard dimensions. Find out the number of ways we can place a black and a white Knight on this chessboard such that they cannot attack each other.
Note:
The knights have to be placed on different squares. A knight can move two squares horizontally and one square vertically (L shaped), or two squares vertically and one square horizontally (L shaped). The knights attack each other if one can reach the other in one move.
Example 1:
Input:
N = 2, M = 2
Output: 12 
Explanation: There are 12 ways we can place a black and a white Knight on this chessboard such that they cannot attack each other.
Example 2:
Input:
N = 2, M = 3
Output: 26
Explanation: There are 26 ways we can place a black and a white Knight on this chessboard such that they cannot attack each other.
Your Task:
Your task is to complete the function numOfWays() which takes the chessboard dimensions N and M as inputs and returns the number of ways we can place 2 Knights on this chessboard such that they cannot attack each other. Since this number can be very large, return it modulo 10^{9}+7.
Expected Time Complexity: O(N*M).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N * M <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3





#Function to find out the number of ways we can place a black and a white

#Knight on this chessboard such that they cannot attack each other.

def numOfWays(M, N):

    # code here

Solutions:
def numOfWays(M, N):
	total = M * N
	total = M * N
	ans = 0
	for i in range(M):
		for j in range(N):
			temp = allAttackingPositions(i, j, M, N) + 1
			ans += total - temp
	return ans % 1000000007

def allAttackingPositions(i, j, M, N):
	dirs = [(2, 1), (2, -1), (-2, 1), (-2, -1), (-1, 2), (1, 2), (-1, -2), (1, -2)]
	count = 0
	for (x, y) in dirs:
		if isValid(i + x, j + y, M, N):
			count += 1
	return count

def isValid(x, y, M, N):
	return 0 <= x < M and 0 <= y < N


def numOfWays(M, N):
	sum = 0
	for i in range(N):
		for j in range(M):
			c = 0
			for (ii, jj) in [(i + 1, j + 2), (i + 1, j - 2), (i - 1, j + 2), (i - 1, j - 2), (i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1)]:
				if ii < N and ii >= 0 and (jj < M) and (jj >= 0):
					c += 1
			sum += N * M - 1 - c
			sum %= 1000000007
	return sum


def numOfWays(M, N):
	if M <= 2 and N <= 2:
		sq = M * N
		return sq * (sq - 1)
	elif M < 2 or N < 2:
		sq = N * M
		return sq * (sq - 1)
	else:
		k1 = M * N
		k2 = M * N - 1
		ktot = k1 * k2
		attack = 4 * ((N - 1) * (M - 2) + (M - 1) * (N - 2))
		return (ktot - attack) % (10 ** 9 + 7)


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

def numOfWays(M, N):
	mod = 1000000007
	ans = 0
	dirs = [[1, 2], [-1, 2], [1, -2], [-1, -2], [2, 1], [-2, 1], [2, -1], [-2, -1]]
	for i in range(N):
		for j in range(M):
			total = N * M
			minus = 1
			for x in dirs:
				if valid(i + x[0], j + x[1], N, M):
					minus += 1
			total -= minus
			ans = (ans + total) % mod
	return ans % mod


def numOfWays(M, N):
	ways = 0
	mod = 10 ** 9 + 7
	dii = [-2, -2, -1, -1, 1, 1, 2, 2]
	djj = [-1, 1, -2, 2, -2, 2, -1, 1]
	for i in range(M):
		for j in range(N):
			safe = M * N - 1
			for k in range(8):
				di = dii[k]
				dj = djj[k]
				if is_valid_cell(i + di, j + dj, M, N):
					safe -= 1
			ways += safe
			if ways >= mod:
				ways %= mod
	return ways

def is_valid_cell(i, j, m, n):
	return 0 <= i < m and 0 <= j < n


def numOfWays(M, N):
	sum = 0
	for i in range(N):
		for j in range(M):
			count = 0
			for (new_i, new_j) in [(i + 1, j + 2), (i + 1, j - 2), (i - 1, j + 2), (i - 1, j - 2), (i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1)]:
				if new_i < N and new_i >= 0 and (new_j < M) and (new_j >= 0):
					count += 1
			sum += N * M - 1 - count
			sum %= 1000000007
	return sum


def numOfWays(M, N):
	ans = (N * M - 1) * N * M
	if N >= 1 and M >= 2:
		ans -= 4 * (N - 1) * (M - 2)
	if N >= 2 and M >= 1:
		ans -= 4 * (N - 2) * (M - 1)
	return ans % 1000000007


def issafe(x, y, n, m):
	return x >= 0 and y >= 0 and (x < n) and (y < m)

def numOfWays(M, N):
	x = [-2, -2, -1, 1, 2, 2, 1, -1]
	y = [-1, 1, 2, 2, 1, -1, -2, -2]
	ans = 0
	for i in range(N):
		for j in range(M):
			res = 1
			for k in range(8):
				if issafe(i + x[k], j + y[k], N, M):
					res += 1
			ans += N * M - res
	return ans % 1000000007


def numOfWays(M, N):
	tot = 0
	g = M * N
	for i in range(N):
		for j in range(M):
			count = 0
			for k in [2, -2]:
				for l in [1, -1]:
					if i + k >= 0 and i + k < N and (j + l >= 0) and (j + l < M):
						count += 1
			for k in [1, -1]:
				for l in [2, -2]:
					if i + k >= 0 and i + k < N and (j + l >= 0) and (j + l < M):
						count += 1
			tot += g - 1 - count
	return tot % 1000000007


def numOfWays(M, N):
	mod = 10 ** 9 + 7
	x = [1, 1, -1, -1, 2, 2, -2, -2]
	y = [2, -2, 2, -2, 1, -1, 1, -1]
	ans = 0
	for i in range(N):
		for j in range(M):
			count = 0
			for k in range(8):
				(row, cl) = (i + x[k], j + y[k])
				if 0 <= row < N and 0 <= cl < M:
					count += 1
			ans += (M * N - count - 1) % mod
	return ans % mod


def numOfWays(M, N):
	count = M * N * (M * N - 1) % (10 ** 9 + 7)
	for i in range(M):
		for j in range(N):
			count -= 0 <= i + 1 < M and 0 <= j + 2 < N
			count -= 0 <= i + 1 < M and 0 <= j - 2 < N
			count -= 0 <= i + 2 < M and 0 <= j + 1 < N
			count -= 0 <= i + 2 < M and 0 <= j - 1 < N
			count -= 0 <= i - 1 < M and 0 <= j + 2 < N
			count -= 0 <= i - 1 < M and 0 <= j - 2 < N
			count -= 0 <= i - 2 < M and 0 <= j + 1 < N
			count -= 0 <= i - 2 < M and 0 <= j - 1 < N
	return count % (10 ** 9 + 7)


def numOfWays(M, N):

	def valid(r, c, N, M):
		return r >= 0 and c >= 0 and (r < N) and (c < M)
	ans = 0
	mod = 10 ** 9 + 7
	dirs = [[1, 2], [-1, 2], [1, -2], [-1, -2], [2, 1], [-2, 1], [2, -1], [-2, -1]]
	for i in range(N):
		for j in range(M):
			curr = N * M
			inval = 1
			for k in dirs:
				if valid(i + k[0], j + k[1], N, M):
					inval += 1
			curr -= inval
			ans += curr
			ans %= mod
	return ans % mod


def numOfWays(M, N):
	count = 0
	res = 0
	squers = M * N
	for i in range(M):
		for j in range(N):
			if -1 < i - 2 < M and -1 < j - 1 < N:
				count += 1
			if -1 < i - 2 < M and -1 < j + 1 < N:
				count += 1
			if -1 < i - 1 < M and -1 < j - 2 < N:
				count += 1
			if -1 < i - 1 < M and -1 < j + 2 < N:
				count += 1
			if -1 < i + 2 < M and -1 < j - 1 < N:
				count += 1
			if -1 < i + 2 < M and -1 < j + 1 < N:
				count += 1
			if -1 < i + 1 < M and -1 < j - 2 < N:
				count += 1
			if -1 < i + 1 < M and -1 < j + 2 < N:
				count += 1
			res = res + count
			count = 0
	res2 = (squers ** 2 - squers - res) % (10 ** 9 + 7)
	return res2


def numOfWays(n, m):

	def issafe(i, j, n, m):
		if i >= 0 and j >= 0 and (i < n) and (j < m):
			return True
		else:
			return False
	dx = [2, 2, -2, -2, 1, 1, -1, -1]
	dy = [1, -1, 1, -1, 2, -2, 2, -2]
	total = n * m
	ans = 0
	for i in range(n):
		for j in range(m):
			blk = 0
			for d in range(8):
				nx = i + dx[d]
				ny = j + dy[d]
				if issafe(nx, ny, n, m) == True:
					blk += 1
			ans += n * m - 1 - blk
	return ans % 1000000007


def valid(i, j, N, M):
	if i >= 0 and j >= 0 and (i < N) and (j < M):
		return True
	return False

def numOfWays(M, N):
	mod = 1000000007
	ans = 0
	dirs = [[1, 2], [-1, 2], [1, -2], [-1, -2], [2, 1], [-2, 1], [2, -1], [-2, -1]]
	mul = M * N
	count = 1
	for i in range(N):
		for j in range(M):
			for d in dirs:
				if valid(i + d[0], j + d[1], N, M):
					count += 1
			ans = (ans % mod + (mul - count)) % mod
			count = 1
	return ans


def numOfWays(M, N):
	number = M * N * (M * N - 1)
	for i in range(M):
		for j in range(N):
			for (ip, jp) in zip([2, 2, 1, -1, -1, 1, -2, -2], [-1, 1, -2, -2, 2, 2, 1, -1]):
				x = i + ip
				y = j + jp
				if 0 <= x and x < M and (0 <= y) and (y < N):
					number -= 1
	return int(number % (10 ** 9 + 7))


def numOfWays(M, N):
	cnt = M * N * (M * N - 1)
	for row in range(M):
		for col in range(N):
			if row - 1 >= 0:
				if col - 2 >= 0:
					cnt -= 1
				if col + 2 < N:
					cnt -= 1
				if row - 2 >= 0:
					if col - 1 >= 0:
						cnt -= 1
					if col + 1 < N:
						cnt -= 1
			if row + 1 < M:
				if col - 2 >= 0:
					cnt -= 1
				if col + 2 < N:
					cnt -= 1
				if row + 2 < M:
					if col - 1 >= 0:
						cnt -= 1
					if col + 1 < N:
						cnt -= 1
	return cnt % (10 ** 9 + 7)


def numOfWays(M, N):
	attack_offsets = [(2, -1), (2, 1), (-2, -1), (-2, 1), (-1, 2), (1, 2), (-1, -2), (1, -2)]
	all_tiles = M * N
	counter = all_tiles * (all_tiles - 1)
	for (km, kn) in attack_offsets:
		n_attack_sources = handle_offset(M, N, km, kn)
		counter -= n_attack_sources
	return counter % (10 ** 9 + 7)

def handle_offset(M, N, km, kn):
	m_min = max(1, 1 - km)
	m_max = min(M, M - km)
	n_min = max(1, 1 - kn)
	n_max = min(N, N - kn)
	m_count = max(0, m_max - m_min + 1)
	n_count = max(0, n_max - n_min + 1)
	n_attack_sources = m_count * n_count
	return n_attack_sources


def numOfWays(m, n):
	dx = [-1, -2, -2, -1, 1, 2, 2, 1]
	dy = [-2, -1, 1, 2, 2, 1, -1, -2]
	modd = 1000000007
	atk = 0
	total = m * n % modd * (m * n - 1) % modd % modd
	for i in range(m):
		for j in range(n):
			for k in range(len(dx)):
				x = i + dx[k]
				y = j + dy[k]
				if x >= 0 and x < m and (y >= 0) and (y < n):
					atk = atk + 1
	return total - atk


def numOfWays(M, N):
	ans = 0
	total = M * N
	mod = pow(10, 9) + 7
	dirt = [[2, 1], [-2, 1], [-2, -1], [2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
	for i in range(M):
		for j in range(N):
			count = 0
			for (x, y) in dirt:
				if 0 <= i + x < M and 0 <= y + j < N:
					count += 1
			ans += (total - 1 - count) % mod
			ans = ans % mod
	return ans


def numOfWays(m, n):
	dx = [-2, -2, -1, 1, 2, 2, 1, -1]
	dy = [-1, 1, 2, 2, 1, -1, -2, -2]
	ans = 0
	for i in range(n):
		for j in range(m):
			c = n * m - 1
			for k in range(8):
				nr = i + dx[k]
				nc = j + dy[k]
				if nr >= 0 and nc >= 0 and (nr < n) and (nc < m):
					c -= 1
			ans += c
	return ans % (10 ** 9 + 7)


def numOfWays(M, N):
	(total, squares) = (0, N * M)
	for x in range(N):
		for y in range(M):
			temp = squares - 1
			if -1 < x - 2 < N:
				if -1 < y - 1 < M:
					temp -= 1
				if -1 < y + 1 < M:
					temp -= 1
			if -1 < x - 1 < N:
				if -1 < y - 2 < M:
					temp -= 1
				if -1 < y + 2 < M:
					temp -= 1
			if -1 < x + 1 < N:
				if -1 < y - 2 < M:
					temp -= 1
				if -1 < y + 2 < M:
					temp -= 1
			if -1 < x + 2 < N:
				if -1 < y - 1 < M:
					temp -= 1
				if -1 < y + 1 < M:
					temp -= 1
			total = (total + temp) % (10 ** 9 + 7)
	return total


def numOfWays(M, N):
	(tot, sqr) = (0, N * M)
	for x in range(N):
		for y in range(M):
			temp = sqr - 1
			if -1 < x - 2 < N:
				if -1 < y - 1 < M:
					temp -= 1
				if -1 < y + 1 < M:
					temp -= 1
			if -1 < x - 1 < N:
				if -1 < y - 2 < M:
					temp -= 1
				if -1 < y + 2 < M:
					temp -= 1
			if -1 < x + 1 < N:
				if -1 < y - 2 < M:
					temp -= 1
				if -1 < y + 2 < M:
					temp -= 1
			if -1 < x + 2 < N:
				if -1 < y - 1 < M:
					temp -= 1
				if -1 < y + 1 < M:
					temp -= 1
			tot = (tot + temp) % (10 ** 9 + 7)
	return tot


import numpy as np

def numOfWays(M, N):
	positions = []
	for x in range(M):
		for y in range(N):
			if x < 2 or y < 2 or x >= M - 2 or (y >= N - 2):
				positions.append((x, y))
	attacking_pos = [(1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1)]
	count = N * M * (N * M - 1)
	for pos in positions:
		for attack in attacking_pos:
			dyn = (pos[0] + attack[0], pos[1] + attack[1])
			if dyn[0] >= 0 and dyn[1] >= 0 and (dyn[0] < M) and (dyn[1] < N):
				count -= 1
	count -= 8 * max(0, M - 4) * max(0, N - 4)
	return count % (10 ** 9 + 7)


def numOfWays(m, n):

	def helper(i, j, n, m):
		x8 = [2, 2, -2, -2, -1, 1, -1, 1]
		y8 = [1, -1, 1, -1, -2, -2, 2, 2]
		c = 1
		for d in range(8):
			nx = i + x8[d]
			ny = j + y8[d]
			if nx >= 0 and ny >= 0 and (nx < n) and (ny < m):
				c += 1
		return n * m - c
	res = 0
	for i in range(n):
		for j in range(m):
			res += helper(i, j, n, m)
			res = res % 1000000007
	return res


def numOfWays(M, N):
	a = (M - 1) * (N - 2)
	b = (N - 1) * (M - 2)
	if a <= 0:
		a = 0
	if b <= 0:
		b = 0
	c = N * M * (N * M - 1)
	c = c - 4 * (a + b)
	return c % 1000000007


from math import factorial, ceil

def numOfWays(M, N):
	tot_pos = N * M * (N * M - 1)
	exe_pos = 0
	for x in range(N):
		for y in range(M):
			for (new_x, new_y) in [(x + 1, y + 2), (x + 1, y - 2), (x - 1, y + 2), (x - 1, y - 2), (x + 2, y + 1), (x + 2, y - 1), (x - 2, y + 1), (x - 2, y - 1)]:
				if new_x < N and new_x >= 0 and (new_y < M) and (new_y >= 0):
					exe_pos += 1
	return int((tot_pos - exe_pos) % 1000000007)


def numOfWays(M, N):
	total = 0
	for i in range(N):
		for j in range(M):
			temp = N * M - 1
			if -1 < i - 2 < N:
				if -1 < j - 1 < M:
					temp -= 1
				if -1 < j + 1 < M:
					temp -= 1
			if -1 < i - 1 < N:
				if -1 < j - 2 < M:
					temp -= 1
				if -1 < j + 2 < M:
					temp -= 1
			if -1 < i + 2 < N:
				if -1 < j - 1 < M:
					temp -= 1
				if -1 < j + 1 < M:
					temp -= 1
			if -1 < i + 1 < N:
				if -1 < j - 2 < M:
					temp -= 1
				if -1 < j + 2 < M:
					temp -= 1
			total = (total + temp) % (10 ** 9 + 7)
	return total


def numOfWays(M, N):
	xdir = [-2, -2, -1, 1, 2, 2, 1, -1]
	ydir = [-1, 1, 2, 2, 1, -1, -2, -2]
	pos = 0
	for _ in range(M):
		for i in range(N):
			for j in range(8):
				x = _ + xdir[j]
				y = i + ydir[j]
				if x >= 0 and x < m and (y >= 0) and (y < n):
					pos += 1
	temp = M * N * (M * n - 1) % (10 ** 9 + 7)
	return (temp + (10 ** 9 + 7) - pos) % (10 ** 9 + 7)


def numOfWays(M, N):
	MOD = 10 ** 9 + 7
	res = M * N * (M * N - 1) % MOD
	if M > 2 and N > 1:
		res -= 4 * (N - 1) * (M - 2) % MOD
		res %= MOD
	if N > 2 and M > 1:
		res -= 4 * (M - 1) * (N - 2) % MOD
		res %= MOD
	return res


def numOfWays(M, N):
	res = 0
	directions = [(1, 2), (-1, 2), (2, -1), (-1, -2), (1, -2), (-2, 1), (2, 1), (-2, -1)]
	for i in range(M):
		for j in range(N):
			curr = M * N - 1
			for (xn, yn) in directions:
				nx = i + xn
				ny = j + yn
				if 0 <= nx < M and 0 <= ny < N:
					curr -= 1
			res += curr % 1000000007
	return res % 1000000007


def numOfWays(M, N):
	ans = (N * M - 1) * (N * M)
	if N >= 1 and M >= 2:
		ans -= 4 * (N - 1) * (M - 2)
	if N >= 2 and M >= 1:
		ans -= 4 * (N - 2) * (M - 1)
	return ans % (10 ** 9 + 7)


def numOfWays(M, N):
	mx = M * N - 1
	MOD = 10 ** 9 + 7
	res = 0
	for i in range(M):
		for j in range(N):
			res += mx
			for (x, y) in [[2, 1], [2, -1], [-2, 1], [-2, -1], [-1, -2], [-1, 2], [1, -2], [1, 2]]:
				(nx, ny) = (i + x, j + y)
				if 0 <= nx < M and 0 <= ny < N:
					res -= 1
			res %= MOD
	return res


def numOfWays(M, N):
	sum = 0
	for x in range(N):
		for j in range(M):
			count = 0
			for (new_x, new_j) in [(x + 1, j + 2), (x + 1, j - 2), (x - 1, j + 2), (x - 1, j - 2), (x + 2, j + 1), (x + 2, j - 1), (x - 2, j + 1), (x - 2, j - 1)]:
				if new_x < N and new_x >= 0 and (new_j < M) and (new_j >= 0):
					count += 1
			sum += N * M - 1 - count
			sum %= 1000000007
	return sum


def numOfWays(M, N):
	total = M * N
	res = 0
	points = [[-1, -2], [-2, -1], [-2, 1], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]
	for i in range(N):
		for j in range(M):
			to = total - 1
			for po in points:
				x = i + po[0]
				y = j + po[1]
				if x >= 0 and x < N and (y >= 0) and (y < M):
					to -= 1
			res = (res + to) % 1000000007
	return res


def numOfWays(m, n):
	ways = 0
	sm = 0
	box = n * m
	temp = box
	for i in range(n):
		box = temp
		for j in range(m):
			box -= 1
			if i + 2 < n and j + 1 < m:
				box -= 1
			if i + 2 < n and j - 1 > -1:
				box -= 1
			if i - 2 > -1 and j + 1 < m:
				box -= 1
			if i - 2 > -1 and j - 1 > -1:
				box -= 1
			if i + 1 < n and j + 2 < m:
				box -= 1
			if i - 1 > -1 and j + 2 < m:
				box -= 1
			if i + 1 < n and j - 2 > -1:
				box -= 1
			if i - 1 > -1 and j - 2 > -1:
				box -= 1
			sm += box
			box = temp
	return sm % 1000000007