Given a matrix with dimensions N x M, entirely filled with zeroes except for one position at co-ordinates X and Y containing '1'. Find the minimum number of iterations in which the whole matrix can be filled with ones.
Note: In one iteration, '1' can be filled in the 4 neighbouring elements of a cell containing '1'.
Example 1:
Input:
N = 2, M = 3
X = 2, Y = 3
Output: 3 
Explanation: 3 is the minimum possible 
number of iterations in which the
matrix can be filled.
Example 2:
Input:
N = 1, M = 1
X = 1, Y = 1 
Output: 0
Explanation: The whole matrix is 
already filled with ones.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minIterations() which takes the dimensions of the matrix N and M and the co-ordinates of the initial position of '1' ie X and Y as input parameters and returns the minimum number of iterations required to fill the matrix.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N, M ≤ 10^{3}
1^{ }≤ X ≤ N
1 ≤ Y ≤ M

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph traversal

Mathematics

Starter code: #User function Template for python3



class Solution:

    def minIteration(self, N, M, x, y):

        #code here

Solutions:
class Solution:

	def minIteration(self, N, M, x, y):
		leftDistance = y - 1
		rightDistance = M - y
		topDistance = x - 1
		bottomDistance = N - x
		maxHor = max(leftDistance, rightDistance)
		maxVer = max(topDistance, bottomDistance)
		return maxHor + maxVer


class Solution:

	def minIteration(self, N, M, x, y):
		answer = 0
		x = x - 1
		y = y - 1
		for i in range(N):
			for j in range(M):
				answer = max(answer, abs(x - i) + abs(y - j))
		return answer


class Solution:

	def minIteration(self, N, M, x, y):
		max_x_dist = max(x - 1, N - x)
		max_y_dist = max(y - 1, M - y)
		return max_x_dist + max_y_dist


class Solution:

	def minIteration(self, N, M, x, y):
		if N * M == 1:
			return 0
		down = N - x
		right = M - y
		return max(x + y - 2, x - 1 + right, down + y - 1, down + right)


class Solution:

	def minIteration(self, N, M, x, y):
		corners = [[0, 0], [0, N - 1], [M - 1, 0], [M - 1, N - 1]]
		mdist = 0
		X = x - 1
		Y = y - 1
		mdist = max(mdist, X + Y)
		mdist = max(mdist, N - (X + 1) + Y)
		mdist = max(mdist, X + (M - (Y + 1)))
		mdist = max(mdist, N - (X + 1) + (M - (Y + 1)))
		return mdist


class Solution:

	def minIteration(self, N, M, x, y):
		if N == 1 and M == 1:
			return 0
		x -= 1
		y -= 1
		topLeft = x + y
		bottomLeft = N - x - 1 + y
		topRight = x + (M - y - 1)
		bottomRight = N - x - 1 + (M - y - 1)
		return max(topLeft, bottomLeft, topRight, bottomRight)


class Solution:

	def minIteration(self, N, M, x, y):
		return max(x + y - 2, abs(x - N) + y - 1, abs(y - M) + x - 1, abs(x - N) + abs(y - M))


from collections import deque

class Solution:

	def minIteration(self, N, M, x, y):

		def bfs():
			vis = [[0] * M for _ in range(N)]
			q = deque([(x, y, 0)])
			vis[x][y] = 1
			while q:
				(a, b, d) = q.popleft()
				for (i, j) in zip((-1, 0, 0, 1), (0, -1, 1, 0)):
					(nx, ny) = (a + i, b + j)
					if 0 <= nx < N and 0 <= ny < M and (not vis[nx][ny]):
						vis[nx][ny] = 1
						q.append((nx, ny, d + 1))
			return d
		ans = 0
		a = max(x - 1, N - x)
		b = max(y - 1, M - y)
		ans = a + b
		return ans


class Solution:

	def minIteration(self, N, M, x, y):
		if N == 1 and M == 1:
			return 0
		res = 0
		x -= 1
		y -= 1
		N -= 1
		M -= 1
		res = max(res, x + y)
		res = max(res, abs(x - N) + y)
		res = max(res, x + abs(y - M))
		res = max(res, abs(x - N) + abs(y - M))
		return res


class Solution:

	def minIteration(self, N, M, x, y):
		if N == 1 and M == 1:
			return 0
		e = max(x + y - 2, N - x + y - 1, M - y + x - 1, N + M - x - y)
		return e


class Solution:

	def findMinIterationFromPosition(self, row, col, x, y):
		return abs(row - x) + abs(y - col)

	def minIteration(self, N, M, x, y):
		min_iteration = 0
		extreme_points = [[1, 1], [1, M], [N, 1], [N, M]]
		for (row, col) in extreme_points:
			min_iteration = max(min_iteration, self.findMinIterationFromPosition(row, col, x, y))
		return min_iteration


class Solution:

	def minIteration(self, N, M, x, y):
		dp = [[N * M] * M for i in range(N)]
		dp[x - 1][y - 1] = 0
		return max(x - 1 + y - 1, M - y + N - x, M - y + x - 1, N - x + y - 1)


class Solution:

	def _2quarter(self, N, M, x, y, dp):
		max_iterations = 0
		for i in range(x - 1, -1, -1):
			for j in range(y - 1, -1, -1):
				if i - 1 >= 0:
					dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + 1)
				if j - 1 >= 0:
					dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + 1)
				max_iterations = max(max_iterations, dp[i][j])
		return max_iterations

	def _4quarter(self, N, M, x, y, dp):
		max_iterations = 0
		for i in range(x - 1, N):
			for j in range(y - 1, M):
				if i + 1 < N:
					dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1)
				if j + 1 < M:
					dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1)
				max_iterations = max(max_iterations, dp[i][j])
		return max_iterations

	def _3quarter(self, N, M, x, y, dp):
		max_iterations = 0
		for i in range(x - 1, N):
			for j in range(y - 1, -1, -1):
				if i + 1 < N:
					dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1)
				if j - 1 >= 0:
					dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + 1)
				max_iterations = max(max_iterations, dp[i][j])
		return max_iterations

	def _1quarter(self, N, M, x, y, dp):
		max_iterations = 0
		for i in range(x - 1, -1, -1):
			for j in range(y - 1, M):
				if j + 1 < M:
					dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1)
				if i - 1 >= 0:
					dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + 1)
				max_iterations = max(max_iterations, dp[i][j])
		return max_iterations

	def minIteration(self, N, M, x, y):
		dp = [[N * M] * M for i in range(N)]
		dp[x - 1][y - 1] = 0
		return max(x - 1 + y - 1, M - y + N - x, M - y + x - 1, N - x + y - 1)


class Solution:

	def minIteration(self, R, C, x, y):
		x -= 1
		y -= 1
		lh = y
		rh = C - y - 1
		tv = x
		bv = R - x - 1
		return max(lh, rh) + max(tv, bv)


class Solution:

	def minIteration(self, N, M, x, y):
		distx = max(x - 1, N - x)
		disty = max(y - 1, M - y)
		return distx + disty


class Solution:

	def minIteration(self, N, M, x, y):
		x = x - 1
		y = y - 1
		N = N - 1
		M = M - 1
		a = max(x + y, N - x + (M - y))
		b = max(x + (M - y), N - x + y)
		return max(a, b)


from collections import deque

class Solution:

	def minIteration(self, N, M, x, y):
		if N == 1 and M == 1:
			return 0
		ans = 0
		X = x - 1
		Y = y - 1
		ans = max(ans, X + Y)
		ans = max(ans, N - (X + 1) + Y)
		ans = max(ans, X + (M - (Y + 1)))
		ans = max(ans, N - (X + 1) + (M - (Y + 1)))
		return ans


from collections import deque

class Solution:

	def minIteration(self, N, M, x, y):
		top = x - 1
		down = N - x
		left = y - 1
		right = M - y
		return max(top, down) + max(left, right)


class Solution:

	def minIteration(self, n, m, x, y):
		return max(n - x + y - 1, n - x + m - y, x - 1 + y - 1, x - 1 + m - y)


class Solution:

	def minIteration(self, n, m, x, y):
		lrud = [y - 1, m - y, x - 1, n - x]
		return max(lrud[0], lrud[1]) + max(lrud[2], lrud[3])


class Solution:

	def minIteration(self, N, M, x, y):
		top = x - 1
		down = N - x
		left = y - 1
		right = M - y
		return max(top + left, max(top + right, max(down + left, down + right)))


class Solution:

	def minIteration(self, N, M, x, y):
		count = 0
		if N == 1 and M == 1:
			return 0
		top = x - 1
		down = N - x
		left = y - 1
		right = M - y
		return max(top + left, max(top + right, max(down + left, down + right)))


import collections

class Solution:

	def minIteration(self, N, M, x, y):
		ans = 0
		for i in range(N):
			for j in range(M):
				ans = max(ans, abs(i + 1 - x) + abs(j + 1 - y))
		return ans


from collections import deque

class Solution:

	def minIteration(self, N, M, x, y):
		return max(max(x + y - 2, y + N - 1 - x), max(x + M - y - 1, N - x + M - y))


from queue import Queue

class Solution:

	def minIteration(self, N, M, x, y):
		ans = 0
		for i in range(1, N + 1):
			for j in range(1, M + 1):
				ans = max(ans, abs(x - i) + abs(y - j))
		return ans


class Solution:

	def minIteration(self, N, M, t, p):
		return max(max(t + p - 2, p + N - 1 - t), max(t + M - p - 1, N - t + M - p))


from collections import deque

class Solution:

	def minIteration(self, N, M, x, y):
		x = x - 1
		y = y - 1
		t1 = x - 0 + y - 0
		t2 = N - x - 1 + y - 0
		t3 = N - x - 1 + M - y - 1
		t4 = x - 0 + M - y - 1
		return max(0, t1, t2, t3, t4)