Question and Answer from L4-M2
from collections import deque
def bride_hunt(matrix):
n = len(matrix)
m = len(matrix[0])
dirs = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
dist = [[-1]*m for _ in range(n)]
q = deque([(0,0)])
dist[0][0] = 0
while q:
x,y = q.popleft()
for dx,dy in dirs:
nx, ny = x+dx, y+dy
if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1:
dist[nx][ny] = dist[x][y] + 1
q.append((nx,ny))
brides = []
for i in range(n):
for j in range(m):
if matrix[i][j] == 1 and not (i==0 and j==0):
qualities = 0
for dx,dy in dirs:
ni, nj = i+dx, j+dy
if 0 <= ni < n and 0 <= nj < m and matrix[ni][nj] != 0:
if not (ni==0 and nj==0):
qualities += 1
if qualities > 0:
brides.append((qualities, dist[i][j], i+1, j+1))
if not brides:
return "No suitable girl found"
max_q = max(b[0] for b in brides)
candidates = [b for b in brides if b[0] == max_q]
min_d = min(b[1] for b in candidates)
final = [b for b in candidates if b[1] == min_d]
if len(final) > 1:
return "Polygamy not allowed"
q, d, r, c = final[0]
return f"{r}:{c}:{q}"
n,m = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(n)]
print(bride_hunt(matrix))