Deloitte | COGNIZANT | IBM | CAPGEMINI
def findOptimalPair(n, m, blockedPositions):
from collections import deque
grid = [[0] * m for _ in range(n)]
b = set()
for r, c in blockedPositions:
b.add((r - 1, c - 1))
grid[r - 1][c - 1] = -1
d = [[float('inf')] * m for _ in range(n)]
queue = deque()
for r, c in b:
queue.append((r, c))
d[r][c] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and (nr, nc) not in b:
if d[nr][nc] > d[r][c] + 1:
d[nr][nc] = d[r][c] + 1
queue.append((nr, nc))
def solve(min_strength):
visited = [[False] * m for _ in range(n)]
if (0, 0) in b or d[0][0] < min_strength:
return -1
q = deque()
q.append((0, 0, 1))
visited[0][0] = True
while q:
r, c, steps = q.popleft()
if (r, c) == (n - 1, m - 1):
return steps
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc] and (nr, nc) not in b:
if d[nr][nc] >= min_strength:
visited[nr][nc] = True
q.append((nr, nc, steps + 1))
return -1
low, high = 0, n + m
bs, ms = -1, -1
while low <= high:
mid = (low + high) // 2
ans = solve(mid)
if ans != -1:
bs = mid
ms = ans
low = mid + 1
else:
high = mid - 1
if bs == -1:
return [-1, -1]
return [bs, ms]
#CISCO
findOptimalPair✅
1.1K ·